Goldbaches Vermutung



  • Servus!

    die Golbachse Vermutung besagt ja:

    Es gibt für jede natürliche Zahl >= 2 die möglichkeit sie in zwe Prinzahlen ( p und q ) zu zerlegen:

    n = p + q

    wie kann ich jetzt beweisen das Problem zu NP gehört?

    Sind hier Fachleute was sowas angeht zu finden? 🙂

    Gruß

    🙂 PaFFy



  • Welches Problem genau meinst Du? Goldbachs Vermutung ist eine Aussage, die ist entweder wahr oder falsch.



  • Das Problem, diese Aussage zu beweisen oder zu widerlegen natürlich.



  • PaFF schrieb:

    Es gibt für jede natürliche Zahl >= 2 die möglichkeit sie in zwe Prinzahlen ( p und q ) zu zerlegen:

    n = p + q

    aha?
    fangen wir vorne an, in welche primzahlen würdest du n = 2 zerlegen?



  • Optimizer schrieb:

    Das Problem, diese Aussage zu beweisen oder zu widerlegen natürlich.

    Da es nur eine Probleminstanz gibt ist dieses Problem aber kein Gegenstand der Komplexitätstheorie.



  • borg schrieb:

    PaFF schrieb:

    Es gibt für jede natürliche Zahl >= 2 die möglichkeit sie in zwe Prinzahlen ( p und q ) zu zerlegen:

    n = p + q

    aha?
    fangen wir vorne an, in welche primzahlen würdest du n = 2 zerlegen?

    1+1, beides keine Primzahl, andere Möglichkeiten gibt es nicht, qed.
    Das war leicht. Was bekomme ich nun für die Widerlegung der Goldbachschen Vermutung? 😃
    Dass der alte Goldbach da nicht selber dran gedacht hat...

    Spaß beiseite, richtig muss es natürlich heißen:
    Jede gerade Zahl größer als 2 kann als Summe zweier Primzahlen geschrieben werden.



  • Bashar schrieb:

    Optimizer schrieb:

    Das Problem, diese Aussage zu beweisen oder zu widerlegen natürlich.

    Da es nur eine Probleminstanz gibt ist dieses Problem aber kein Gegenstand der Komplexitätstheorie.

    Ja, vermutlich hat es eher was mit Berechenbarkeit zu tun.



  • Optimizer schrieb:

    Bashar schrieb:

    Optimizer schrieb:

    Das Problem, diese Aussage zu beweisen oder zu widerlegen natürlich.

    Da es nur eine Probleminstanz gibt ist dieses Problem aber kein Gegenstand der Komplexitätstheorie.

    Ja, vermutlich hat es eher was mit Berechenbarkeit zu tun.

    Ne, damit hat es auch nix zu tun. Entweder die Behauptung ist wahr, dann kann man die Zerlegung auch leicht durch ausprobieren aller kleineren Primzahlen berechnen. Oder die Behauptung ist eben falsch, dann kann man auch nix machen.

    Sogar die Funktion

    f(n) = {1, wenn goldbachs vermutung stimmt, 0 sonst

    ist berechenbar. Wir wissen nur leider nicht, ob es die 0- oder die 1-Funktion ist.



  • naja es ging um die Frage ob dieses Problem zu P oder NP gehört und wie man das beweisen könnte...



  • einPhysiker schrieb:

    Spaß beiseite, richtig muss es natürlich heißen:
    Jede gerade Zahl größer als 2 kann als Summe zweier Primzahlen geschrieben werden.

    Spaß hin oder her... Was ist mit der 3???


  • Mod

    WebFritzi schrieb:

    einPhysiker schrieb:

    Spaß beiseite, richtig muss es natürlich heißen:
    Jede gerade Zahl größer als 2 kann als Summe zweier Primzahlen geschrieben werden.

    Spaß hin oder her... Was ist mit der 3???

    3 ist keine gerade Zahl.


  • Mod

    xPaFF schrieb:

    naja es ging um die Frage ob dieses Problem zu P oder NP gehört und wie man das beweisen könnte...

    Gleich am Anfang wurde schon gefragt: Welches Problem meinst du?

    Die Goldbachsche Vermutung ist eine Aussage, also entweder wahr oder falsch, und damit kein Problem, das man einer Komplexitätsklasse zuordnen kann.



  • ja stimmt es geht um jede gerade Zahl...sorry

    also diese Aussage stellt ein Endscheidungsproblem dar( Eben ob sie gilt oder nicht )...und die Frage ist ob dieses Endscheidungsproblem zu P oder NP gehört...


  • Mod

    xPaFF schrieb:

    also diese Aussage stellt ein Endscheidungsproblem dar( Eben ob sie gilt oder nicht )...und die Frage ist ob dieses Endscheidungsproblem zu P oder NP gehört...

    Wie Bashar schon geschrieben hat: Für eine Komplexitätsbetrachtung braucht es mehr als eine Probleminstanz. Denn so lässt sich das natürlich in konstanter Zeit lösen: bool hat_goldbach_recht() kann true oder false in Konstantzeit liefern.



  • Wenn die Zerlegung immer geht, dann kann man sie auch flott berechnen, einfach alle Zerlegungen mit kleineren Primzahlen durchprobieren. Geht es nicht immer, dann ist das Problem auch nicht lösbar und damit weder in P noch in NP. Aber auch das hatte ich eigentlich schon geschrieben.



  • in dem Buch das ich hier habe steht das es zu NP gehört und wenn seine Vermutung wahr wäre dann wäre es in P



  • Dann wird das Buch am besten Weg.



  • ich habe es aber nur ausgeliehen... 😮

    grau ist alle theorie 😡 😡 😡



  • Ich vermute eher, du hast den entsprechenden Abschnitt falsch interpretiert. (lies doch nochmal genauer - und wenn es dann immer noch unklar ist, kannst du den Abschnitt ja mal vorlegen).

    PS: Die Aufgabe "Gegeben ist eine gerade Zahl x - zerlege sie in eine Summe aus zwei Primzahlen" kannst du in Polynomialzeit lösen (bzw. in Polynomialzeit feststellen, wenn es nicht möglich ist).



  • Jester schrieb:

    Wenn die Zerlegung immer geht, dann kann man sie auch flott berechnen, einfach alle Zerlegungen mit kleineren Primzahlen durchprobieren.

    Angenommen die Vermutung stimmt, und man bekommt die Zahl als bitstring der länge n übergeben, dass bedeutet, es sind 2n2^n potentielle Zahlen zu testen. Unter diesen 2n2^n Zahl sind ca. 2nlog(2n)\frac{2^n}{\log(2^n)} Primzahlen. Weiterhin angenommen ich würde diese Primzahlen in O(1) bestimmen können, würde das Durchtesten dann nicht Zeit O(2nlog(2n))=O(2nn)O(\frac{2^n}{\log(2^n)}) = O(\frac{2^n}{n}) benötigen? Wieso ist das denn dann in P?


Log in to reply