Hi !
Ich lerne gerade auf Staatsexamen Mathematik, Teilprüfung Informatik. Jetzt habe ich von der Anschauung her ein Problem mit dem Begriff NP-vollständig.
Im Schöning steht, es würde intuitiv so viel wie „mindestens so schwierig, wie jedes andere Problem in NP“ heißen. Jetzt versuche ich es, mit meinen Worten zu konkretisieren:
Ein NP-vollständiges Problem besitzt für jede nichtdeterministische Turingmaschine und jedes Polynom ein Element der Länge n, dass nicht in O(p(n)) liegt, ist aber grundsätzlich für alle n polynomial beschränkt (müsste dann nicht das begrenzende Polynom von der Größe von n abhängen?)
Ich würde mir das dann so vorstellen, dass zum Beispiel die Rechenzeit aller Elemente der Länge