Zwei offene Probleme gelöst?! |
| 03.10.2007, 01:37 | promath | Auf diesen Beitrag antworten » | ||
| Zwei offene Probleme gelöst?! 1. Das Primzahlproblem ist NP-vollständig (Bit-Komplexität) 2. Das Graphenisomorphieproblem liegt in P Damit liegen beide nicht in NP ohne NP vollständig und P=NP wird wieder wahrscheinlicher. Ich bin mir zwar bei beiden nicht unsicher, eine Lösung gefunden zu haben, aber ganz sicher bin ich auch nicht. Deshalb bleibe ich anonym und habe beide mal ins Netz gestellt: http://promath.pr.ohost.de |
||||
| 03.10.2007, 02:19 | Tobias | Auf diesen Beitrag antworten » | ||
Erstmal ist PRIMES in P: http://www.math.princeton.edu/~annals/is...004/Agrawal.pdf Dann ist glaube ich deine Reduktionsrichtung falsch. Du führst das Problem PRIMES auf SAT zurück und sagst dann: PRIMES ist NP-Vollständigm weil SAT NP-vollständig ist. Das ist ein Trugschluss, denn wer sagt dir, dass es nicht noch andere Reduktionen von PRIMES in ein Problem aus P gibt? Richitg wäre es also, das SAT Problem in ein PRIMES Problem zu überführen, dann kann man nämlich sagen: Falls Primes in P, dann ist auch SAT in P. Dein Isomorphie-Algo ist auch nicht korrekt, denn er würde (so wie ich ihn verstanden habe) für die beiden Graphen (siehe Anhang) Isomorphie feststellen. Isomorphie ist ein stärkeres Kriterium als deine Formulierung "jeder Knoten in G1 mit Grad n hat einen Nachbarknoten mit Grad m gdw. es einen Knoten in G2 mit Grad n gibt, der einen Nachbarknoten mit Grad m hat". Die formale Definition ist und sind isomorph gdw. es eine bijektive Abbildung gibt mit der Eigenschaft .
Völliger Unsinn. 
|
||||
| 13.10.2007, 00:24 | promath | Auf diesen Beitrag antworten » | ||
| Rückrichtung Hallo, OK, die Rückrichtung ist nicht trivial, deshalb gibt es eine neue Version mit intensiverer Dokumentation. Schaut euch die mal an. Ich bleibe anonym, weil ungelöste Probleme fast immer falsch gelöst werden, aber ich finde, wir sollten uns mehr mit sowas beschäftigen. Dein Gegenbeweis für das zweite Problem ist schlüssig. Das Isomorphieproblem bezieht sich auf zusammenhängende Graphen. Kennt ihr auch ein Gegenbeispiel dafür? |
||||
| 13.10.2007, 00:34 | Tobias | Auf diesen Beitrag antworten » | ||
Zu Primes: Wenn das Primzahlproblem bereits (anerkannt) in P liegt, dann hast du damit ja P = NP gezeigt. Ich gratuliere! Zu Graphenisomorphie: Wo steckt in deiner Ausführung das Kriterium "Isomorphie"? |
||||
| 13.10.2007, 14:56 | promath | Auf diesen Beitrag antworten » | ||
| zwei Fehler Ich habe längere Zeit darüber nachgedacht und selber zwei Fehler gefunden: Beim Graphenisomorphieproblem zeige ich (a=>b) und (nicht b => nicht a). Das gilt auch für a falsch und b wahr. In der Rückrichtung des Primzahlproblems reduziere ich von KNF-SAT auf "Zahl hat einen Teiler der Länge n Bits". Das zeigt zwar die NP-Vollständigkeit der Primfaktorzerlegung, was auch neu wäre, wenn es richtig wäre, aber die Reduzierung von "Zahl hat einen Teiler der Länge n Bits" auf "andere Zahl ist Primzahl" ist auf diese Art nicht richtig. Ich bin nicht sicher, ob es eine solche algoritmische polynomielle Reduktion gibt. Vielleicht liegt PRIMES in P und die Primfaktorzerlegung ist NP-vollständig. |
||||
| 13.10.2007, 15:31 | promath | Auf diesen Beitrag antworten » | ||
| 1 verworfen - 1 eingeschränkt Zusammenfassend ist bis jetzt zu sagen: eine Lösung ist definitiv falsch und eine Behauptung wurde eingeschränkt, das wurde jetzt auch auf der Homepage vermerkt. P=NP wurde schonmal nicht bewiesen, aber vielleicht ist das Problem der Primfaktorzerlegung NP-vollständig, was neu wäre. Vielleicht fällt mir oder euch noch ein Fehler auf... |
||||
| Anzeige | ||||
|
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
