Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Beweisidee fuer P != NP
Mir kam grad eine Idee zur P-NP-Frage. Wenn ich mich nicht taeusche, dann kann man zumindest fuer bestimmte Probleme zeigen, dass zugehoerige Algorithmen eine Mindestlaufzeit aufweisen muessen. Beispielsweise hiess es in AuD, dass vergleichsbasiertes Sortieren nicht schneller als in O(n*log(n)) geht. Laesst sich damit nur die “engste” O-Kalkuel-Klasse finden oder geht das (zumindest teilweise) auch fuer ganz konkrete Laufzeiten wie n² + 3?
Die Idee waere nun, ein Problem aus der NP-Welt zu finden, welches ausserhalb von P vermutet wird und eben zu beweisen, dass die Mindestlaufzeit (ob konkret oder im O-Kalkuel sollte ja egal sein) im exponentiellen Bereich liegt.
Das ist jetzt sicher kein revolutionaerer Einfall, liegt ja eigentlich recht nahe. Ich schaetze, das wurde auch schonmal versucht, aber vielleicht kann mir ja jemand begruenden, warum das so schwer oder gar unmoeglich ist? Ich koennte mir vorstellen, dass die (unendlichen?) Moeglichkeiten, das Problem polynomiell auf irgendein anderes zu reduzieren, hier einen Strich durch die Rechnung machen.
Ja, du kannst für viele Probleme die Mindestlaufzeit ganz konkret angeben, meistens in Form von Instruktionen, die ausgeführt werden müssen.
Deine Idee wäre jetzt tatsächlich ein Ansatz, um P != NP zu zeigen (und scheint auch die naheliegendste Idee dafür zu sein). Allerdings kommst du mit den “normalen” Beweistechniken (bewiesenermaßen) nicht weiter, wenn du so einen Beweis tatsächlich führen willst. Daher hat das noch niemand einfach so gemacht. Eigentlich ist das auch einer der interessantesten Aspekte von P != NP, dass man bei der Beschäftigung damit viel über die Grenzen unserer verwendeten Beweistechniken lernt. Neue Beweistechniken gibts aber total selten.
edith sagt: Allerdings brauchst du die genaue Anzahl an Instruktionen garnicht, es in O-Notation zu zeigen würde ausreichen. Eventuell denkst du dir, dass es vielleicht “einfacher” ist, genaue Instruktionszahl anzugeben? Das ist normalerweise nicht der Fall.
Ok, ich verstehe.
Ist denn die Anzahl der moeglichen Poly-Reduktionen fuer jede Sprache in NP unendlich? Das waere doch aequivalent zu der Aussage, dass die Anzahl der NP-vollstaendigen Probleme unendlich ist oder?
Und das muesste sie ja sein, weil man einfach fuer jedes Problem unendlich viele Trivialitaeten dazu erfinden koennte, zB: Man nehme SAT. Dann sagt man SAT1 enthaelt die Woerter w, welche in SAT liegen, gefolgt von einer 1. SAT2 analog mit einer 2 bzw binaer 10 dran etc.
Ist das eine legitime Konstruktion?
Und wenn es dann unendlich viele NP-vollstaendige Probleme gibt, folglich also unendlich viele polynomielle Reduktionen innerhalb von NP, ist es dann ueberhaupt mit der uns bekannten Logik moeglich, die bzw eine kuerzeste zu finden?
Vmtl. ja, denn SAT auf SAT1 zu reduzieren geht ja in O(1) und kuerzer geht es wohl nicht?
(Eine Reduktion einer Sprache auf sich selbst sollte in O(0) liegen oder?)
Denke ja, trivialerweise: Man kann, mit i ∈ ℕ, Algorithmen konstruieren die Laufzeit O(nⁱ) haben (denke zB per Ackermann). Diese abzaehlbar unendlich vielen Algorithmen kannst du an dein spezielles SAT rankleben und kriegst abzaehlbar unendlich viele Varianten. Da ist allerdings die Abkuerzung auf normales SAT auch klar.
Ob man allgemein immer kuerzeste Reduktionen finden kann wuerde ich bezweifeln.
O(1) und O(0) ist dasselbe, daher trivialerweise zweimal ja. Und nix tun braucht konstant keine Rechenzeit.
Ich bin mir nicht sicher, ob O(0) ueberhaupt definiert ist, da dabei eine Null im Nenner staende (bei der Definition mit Limes). Falls man die zweite Definition verwendet, so ist O(0) in O(1) enthalten, doch die Umkehrung ist falsch.
Streng genommen ist es in der Notation undefiniert, andererseits ist 0 auch nur eine (sehr kleine) konstante Zahl. Nachdem es ja sowieso in der Notation darum geht, Konstante wegzuwerfen, zu vernachlaessigen und zu ignorieren ist es nur konsequent, “braucht keine Zeit” zusammenzupacken mit “braucht konstante Zeit”. Auch wenn “braucht keine Zeit” eigentlich ein wirr undefinierter Randfall ist.
Alles klar, danke fuer die Erklaerung.
Norbert Blum hat seinen Beweis(versuch) zurückgezogen.
https://arxiv.org/abs/1708.03486
6 „Gefällt mir“