Lösung des P-NP-Problems?

Vielleicht wirkt es wie eine blöde Frage. Die Frage ist aber durchaus ernst gemeint:

Angenommen, ihr glaubt, das P-NP-Problem gelöst zu haben. Was macht ihr dann?

OK. Schaut euch einmal das hier an.

http://www.hugi.scene.org/adok/articles/pnpproblem.pdf

Zitat von rosquilla

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?

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.

Zitat von rosquilla

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?

Wie ich erklärt habe, ist es ab n = 4 Knoten nicht mehr möglich, eine bestimmte Lösung zu nehmen, die für alle möglichen Graphen mit n = 4 Knoten gültig ist, sondern man muss mindestens 2 verschiedene Lösungsmöglichkeiten überprüfen (denn ich habe gezeigt, dass es mindestens zwei Graphen gibt, deren Lösungsmengen zueinander disjunkt sind). Weiters habe ich gezeigt, dass die Anzahl der Lösungsmöglichkeiten, die überprüft werden müssen, mit linear steigender Knotenzahl exponentiell wächst: Bei n = 4d gibt es 2^d Graphen mit 2^d zueinander disjunkten Lösungsmöglichkeiten. Somit ist die Anzahl der Lösungsmöglichkeiten, die mindestens überprüft werden müssen, um garantiert eine gültige Lösung zu finden, nicht polynomiell, sondern exponentiell von der Anzahl der Knoten (also der Größe der Eingabedaten) abhängig. Das habe ich meines Erachtens hieb- und stichfest bewiesen.

Die einzige Schwachstelle, die ich momentan sehe, ist eben die, dass ich davon ausgehe, dass der bestmögliche Algorithmus, bei dem mit der Methode "durchsuche alle in Betracht kommenden Lösungsmöglichkeiten und überprüfe, ob sie gültig sind, bis die erste gültige Lösung gefunden wurde" vorgegangen wird, nicht schlechter sein kann als irgendein anders aufgebauter Lösungsalgorithmus. Das heißt, ich gehe davon aus, wenn es keinen Algorithmus mit dieser Methode gibt, der eine polynomielle Laufzeit hat, dann kann es keinen andersgearteten Algorithmus für dasselbe Problem geben, der eine polynomielle Laufzeit hat. Diese Annahme habe ich nicht bewiesen. Eventuell wurde sie bereits von jemand anderem bewiesen - wenn das der Fall ist, dann dürfte mein Beweis tatsächlich funktionieren. Sollte aber bewiesen werden können, dass diese Annahme falsch ist, würde meine Argumentation in sich zusammenbrechen.

Zitat von Paulchen

Dir müsste klar sein, dass es für einen mathematischen Beweis nicht ausreicht, ein einzelnes Beispiel zu bringen. Genau das machst du aber. Du bringst ein Beispiel für einen Algorithmus, der dein NP-vollständiges Problem in nicht-polynomieller Laufzeit löst, und behauptest, es kann daher keinen Algorithmus mit polynomieller Laufzeit für dieses Problem geben.

Ich gehe davon aus, dass es keinen Algorithmus geben kann, der das Problem in polynomieller Laufzeit löst, weil der Suchraum (Anzahl der zu untersuchenden Lösungsmöglichkeiten) exponentiell mit der Größe der Eingabedaten (Anzahl der Knoten des Graphen) wächst. Ich beweise, dass der Suchraum tatsächlich exponentiell wächst - dieser Beweis dürfte hieb- und stichfest sein. Was ich nicht beweise, ist, dass es keinen polynomiellen Algorithmus geben kann, wenn der Suchraum exponentiell wächst. Das nehme ich nur an. Wie gesagt, könnte es sein, dass jemand anderer diesen Zusammenhang bewiesen hat. Es könnte auch sein, dass jemand anderer bewiesen hat, dass dieser Zusammenhang nicht besteht - in diesem Fall wäre die Schlussfolgerung P != NP unzulässig. Sollte aber der Zusammenhang beweisbar sein, wäre P != NP die gültige Schlussfolgerung.

Zitat von Paulchen

Darf ich also zusammenfassen: Du schreibst in der Einleitung deines Textes, dass aus P != NP folgt, dass für NP-vollständige Probleme keine Lösungsalgorithmen mit polynomieller Laufzeit existieren. Um zu zeigen, dass P != NP gilt, nimmst du an, dass es für NP-vollständige Probleme keine Lösungsalgorithmen mit polynomieller Laufzeit gibt. Damit hast du zwei Dinge gezeigt:

• Für NP-vollständige Probleme gibt es genau dann keine Lösungsalgorithmen mit polynomieller Laufzeit, wenn es für NP-vollständige Probleme keine Lösungsalgorithmen mit polynomieller Laufzeit gibt.
• P != NP genau dann, wenn P != NP.

Ich kenne jemanden, der noch Leute sucht, um einen Tautologieclub gründen zu können. Soll ich euch bekannt machen?

Diese Argumentation kann ich nicht nachvollziehen. Es gilt P != NP genau dann, wenn, wie du schreibst, "für NP-vollständige Probleme keine Lösungsalgorithmen mit polynomieller Laufzeit existieren". Wenn ich die rechte Seite dieser Gleichung beweisen kann (wobei es in diesem Fall genügt, für ein einziges Problem in NP zu beweisen, dass kein Algorithmus mit polynomieller Laufzeit existieren kann), dann folgt daraus die linke Seite. Das ist keine Tautologie. Derzeit ist weder die linke Seite noch die rechte Seite bewiesen. Es ist aber auch weder die linke Seite noch die rechte Seite widerlegt. Wenn es gelingt, eine der beiden Seiten zu beweisen, dann folgt daraus, dass auch die andere Seite bewiesen ist. Wenn es gelingt, eine der beiden Seiten zu widerlegen, dann folgt daraus, dass auch die andere Seite widerlegt ist. Genau darum geht es im P-NP-Problem.

Zitat von rosquilla

Genau das ist das Problem in deiner Argumentation. Wenn du das beweisen kannst, dann hast du tatsächlich P!=NP gezeigt. Ansonsten nicht.

Genau. Das habe ich selbst erkannt, und da gebe ich dir völlig Recht.

Zitat von Paulchen

Wie wäre es mit Literaturrecherche?

Dazu bin ich zu faul

Zitat von Bradon

Das ist doch genau das, was ein P/NP-Beweis beweisen muesste. Du hoffst also, dass jemand bereits bewiesen hat, dass P ungleich NP ist, damit dein Beweis funktioniert.

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.