1)
Kann mir mal jemand anschaulich erklaeren, was NP-Vollstaendigkeit ist?

Wenn ich das richtig verstanden habe, dann ist eine Sprache genau dann NP-Vollstaendig, wenn sie aus NP ist und sich alle Sprachen aus NP sich auf sie polynomiell reduzieren lassen.
Aber wuerde das denn nicht auch bedeuten, dass alle Sprachen aus NP NP-vollstaendig sind? (ich denke das ist falsch) und wo ist der unterschied zu np-hart?

2)

was hat man davon dass man weiss, dass ein Problem NP-vollstaendig ist im gegensatz dazu, dass es aus P ist und exponentiellen Aufwand braucht?

3)
Ich sehe nicht so richtig den Unterschied zwischen der primitiven und Mue rekursiven Funktionen. Die mue rekursiven haben doch nur noch zusaetzlich diesen Mue-Operator, der guckt wann das erste mal in einer Folgen der wert 0 auftritt? Toll - aber was haben wir davon?

1) Upps.. bei NP-Vollständigkeit ging es um Sprachen?? Ich hatte das so in Erinnerung:
Ein Problem ist genau dann NP-Vollständig, wenn es keinen Algorithmus gibt, der es in polynomialer Laufzeit löst. (NP = non polynomial oder so ähnlich)

2) Wenn ein Problem aus P ist, dann heißt das doch, dass es einen Algorithmus gibt, der in polynomialer Zeit das Problem löst. Also ist er nicht exponentiell…

Ich hoffe mal, ich verwechsle da jetzt nix…

1) Upps.. bei NP-Vollständigkeit ging es um Sprachen?? Ich hatte das so in Erinnerung:
Ein Problem ist genau dann NP-Vollständig, wenn es keinen Algorithmus gibt, der es in polynomialer Laufzeit löst. (NP = non polynomial oder so ähnlich)

Sprache und Problem, das läßt sich doch meist recht gut aufeinander abbilden: Z.b.Ich habe eine Sprache X (in NP) -> das Problem ob ein Wort Y darin ist, ist NP.

Analog kann man sich zu einem Problem in NP eine entsprechende Sprache basteln.

1)
Wenn ich das richtig verstanden habe, dann ist eine Sprache genau dann NP-Vollstaendig, wenn sie aus NP ist und sich alle Sprachen aus NP sich auf sie polynomiell reduzieren lassen.

Jawoll, das steht auch so in den Buechern und im F3-Skript,
nur muss man wissen, was das polynomiell reduzieren ist!

Aber wuerde das denn nicht auch bedeuten, dass alle Sprachen aus NP NP-vollstaendig sind?

Nee, jede endliche Menge ist in NP aber NP-vollstaendige Mengen (z.B. SAT) sind unendlich. wie soll die Reduktion da gehen? Auch waere dann P=NP, und das ist nicht bekannt!

(ich denke das ist falsch) und wo ist der unterschied zu np-hart?

s.o., np-hart ist eine Menge M, wenn sich jedes Problem (=Menge) aus NP auf M reduzieren laesst, M zu akzeptieren kann aber echt schwer sein, z.B. auch nicht mehr primitiv rekursiv!

2)
was hat man davon dass man weiss, dass ein Problem NP-vollstaendig ist im gegensatz dazu, dass es aus P ist und exponentiellen Aufwand braucht?

Wenn P NP-vollstaendig ist, wissen wir NICHT ob es in P ist (Sonst waere P=NP, und das ist noch ungeloest!!) Also: wenn P NP-vollstaendig ist, so kann NIEMAND besser sein als wir mit unserem exponentiellen Algorithmus! Im anderen Fall, koennte die Konkurenz besser sein und den Zuschlag erhalten!

3)
Ich sehe nicht so richtig den Unterschied zwischen der primitiven und Mue rekursiven Funktionen.

Die Mue rekursiven Funktionen entsprechen denen, die Turing Maschinen berechnen koennen, mehr geht nicht. Primitiv rekursiv ist echt weniger, aber fuer praktische Faelle i.d.R. meist immer noch zu schlimm:
f(n) = 2 hoch 2 hoch 2 hoch 2 hoch 2 hoch 1024 hoch n
ist prim. rek. aber das will wohl niemand ausrechnen muessen.

oder anders:
prim. rek. Funktionen lassen sich mit Programmen berechnen,
die lediglich for-Schleifen kennen
mue rek. Funktionen lassen sich mit Programmen berechnen, die
while-Schleifen kennen
Letztere koennen also echt mehr!

… Toll - aber was haben wir davon?

Wissen ist Macht!

Hoppla, da hatte ich das P zweimal unterschiedlich vewendet: Statt:

Wenn P NP-vollstaendig ist, wissen wir NICHT ob es in P ist (Sonst waere P=NP, und das ist noch ungeloest!!) Also: wenn P NP-vollstaendig ist, so kann NIEMAND besser sein als wir mit unserem exponentiellen Algorithmus! Im anderen Fall, koennte die Konkurenz besser sein und den Zuschlag erhalten!

wäre besser gewesen:

Wenn ein Problem X NP-vollstaendig ist, wissen wir NICHT ob X in P ist (Sonst waere P=NP, und das ist noch ungeloest!!) Also: wenn X NP-vollstaendig bewiesen wurde, so kann NIEMAND besser sein als wir mit unserem exponentiellen Algorithmus! Im anderen Fall, koennte die Konkurenz besser sein und den Zuschlag erhalten!

nun verstaendlich?

Danke!
Jetzt ist mir das alles um einiges klarer…