Zwei offene Probleme gelöst?! < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:03 Mi 03.10.2007 | | Autor: | promath |
| Aufgabe | Ist das Primzahlproblem NP-vollständig?
Liegt das Graphenisomorphieproblem in P? |
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: www.matheboard.de unter sonstiges
Komplexitätstheorie
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
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:19 Do 04.10.2007 | | Autor: | felixf |
Hallo!
> Ist das Primzahlproblem NP-vollständig?
Es liegt in P, wie schon seit laengerer Zeit bekannt ist. Google doch einfach mal nach ![[]](/images/popup.gif) ``PRIMES is in P''.
> Liegt das Graphenisomorphieproblem in P?
Ist es nicht auch NP-vollstaendig?
> 1. Das Primzahlproblem ist NP-vollständig
> (Bit-Komplexität)
> 2. Das Graphenisomorphieproblem liegt in P
Wenn auch nur eins davon stimmen sollte, waere bereits P = NP.
> http://promath.pr.ohost.de
Ich habe nur kurz drueber geschaut, glaube aber nicht, dass es funktioniert. Wenn ich mal Zeit hab schau ich vielleicht mal genauer rein...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:52 Do 04.10.2007 | | Autor: | dormant |
Hi!
> 2. Das Graphenisomorphieproblem liegt in P
Du sollst noch zeigen, dass dein Algorithmus in polynomialer Zeit korrekt ausgeführt werden kann. Wenn du das schaffst wärest du um eine Million $ reicher. Aber ich glaub nicht, dass so ein einfacher Beweis übersehen worden war.
Ich persönlich konnte deinen Algorithmus nicht nachvollziehen.
Gruß,
dormant
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:32 Fr 05.10.2007 | | Autor: | SEcki |
> 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:
Soso, anonym? Warum das denn?
> http://promath.pr.ohost.de
Also leicht war es nicht zu lesen, dein Gleichungssystem habe ich nicht ganz verstanden (das bracuht man aber auch nicht, um den Fehler zu sehen)
Nun gut - beide Beweise sind imo falsch. Also:
Prim ist NP vollständig: du reduzierst hier das Problem auf 3KNF - das ist aber trivial, da 3KNF ja NP vollständig ist. Das ist einfach die falsche Richtung - du musst eine belieibge Formel in konjunktiver Normalform in ein Primzahlproblem übersetzen. Das belisbt du schuldig.
Grapheniso ist in P: kurz gesagt: du schaust die die Knoten und alle Nachbarknoten mit deren Kantenzahl an. Du bleibst einen Beweis schuldig, dass 2 Graphen, die dort immer gleich sind, isomorph sind - das ist auch einfach falsch: nimm einen großen Kreis mit 10 Punkten und 2 kleine mit 5 - die sind nicht isomoprh wg. Zushkomponenten erfüllen aber deinen Algorithmus.
SEcki
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:19 Sa 13.10.2007 | | Autor: | promath |
http://promath.pr.ohost.de
Eine genauere Dokumentation der Rückrichtung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:05 Sa 13.10.2007 | | Autor: | promath |
Ok,
ich weiss jetzt was an dem Graphenisomorphiebeweis
falsch ist. Ich zeige (a=>b) und (nicht b => nicht a).
Das gilt auch für a falsch und b wahr.
Und in diese Rubrik fällt das Gegenbeispiel.
Im Primzahlbeweis der Rückrichtung
ist die Reduktion von "Zahl hat Teiler der Länge n Bits"
auf "Zahl ist Primzahl" vermutlich verkehrt.
Aber vielleicht stimmt das erstere.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:33 Sa 13.10.2007 | | Autor: | promath |
In der Rückrichtung reduziere ich von KNF-SAT
auf "Zahl hat Teiler der Länge n Bits".
Wenn es stimmt, wäre zumindest das
Problem der Berechnung der Primteiler
NP-vollständig. PRIMES wäre erst dann
NP-vollständig, wenn eine Zahl berechnet
werden kann, die Primzahl ist, wenn die
zunächst berechnete Zahl einen Teiler der Länge n
Bits hat. Dieser letzte Schluss ist in der
Rückrichtung wohl verkehrt, aber vielleicht kann
man eine solche Zahl berechnen. Vielleicht auch
nicht, dann ist PRIMES in P aber die
Primfaktorzerlegung nicht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:29 Sa 13.10.2007 | | Autor: | promath |
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...
|
|
|
|
