Das würde ich nicht so sagen. Wenn man noch nicht bewiesen hat, dass der Suchraum eine exponentielle untere Schranke hat, kann man nicht sagen, dass das Problem in P liegt. Man müsste dazu zeigen, dass die obere Schranke für den Suchraum polynomiell ist.
Entschuldige, damit hast du natürlich recht.
Naja, dieser Beweis würde alleine eben nicht ausreichen: Man muss (wie ich getan habe) auch noch beweisen, dass der Suchraum für ein konkretes NP-Problem eine exponentielle untere Schranke hat
Das ist trivial. Sonst wäre das Problem ja in P.
(Ich finde du solltest Paulchens Rat bezüglich Literaturrecherche annehmen, sonst kommst du leicht in peinliche Situationen.)
Also, mir war eigentlich nicht klar, dass gerade dieser eine Schritt derjenige ist, der den Forschern auf der ganzen Welt Kopfzerbrechen bereitet. Aber wenn dem so ist: gut, dann kommt noch einiges an Arbeit auf uns zu, bis P != NP bewiesen ist. Doch, wie gesagt, man müsste erst einmal mit einer Literaturrecherche abklären, ob es nicht doch bereits einen Beweis für diesen einen Schritt gibt, bzw. einen Beweis, dass meine Annahme ungültig ist.
Wie gesagt, so ein Beweis würde P!=NP zeigen. Wenn es ihn gäbe und er zugänglich wäre, dann würde das Clay Institut nicht eine Million auf ihn setzen. Es ist natürlich nicht ausgeschlossen, dass es ihn gibt. Gefunden muss er halt werden ;).
Was ich nicht beweise, ist, dass es keinen polynomiellen Algorithmus geben kann, wenn der Suchraum exponentiell wächst. Das nehme ich nur an.
Genau das ist das Problem in deiner Argumentation. Wenn du das beweisen kannst, dann hast du tatsächlich P!=NP gezeigt. Ansonsten nicht.
Ich versuche zu zeigen, dass die untere Schranke der Anzahl der Möglichkeiten, die ich überprüfen muss, exponentiell ist. Man muss nicht alle Möglichkeiten überprüfen, aber in jedem Fall exponentiell viele.
Aus deiner Argumentation geht mE nicht hervor, warum es tatsächlich notwendig ist exponentiell (sorry "alle" war natürlich nicht richtig) viele Möglichkeiten zu überprüfen. Nochmal: Wodurch schliesst du aus, dass ein Algorithmus existiert, der in polynomieller Zeit läuft?
OK. Schaut euch einmal das hier an.
Du behauptest, dass du auf jeden Fall alle Möglichkeiten (exponentiell viele) überprüfen musst. Woher weisst du, dass es keinen Algorithmus gibt, der dir erlaubt nur polynomiell viele zu überprüfen?
