P != NP sehr wahrscheinlich bewiesen!

schranze · 11.08.10, 15:29

Eines der wichtigsten offenen Probleme, mit denen sich Mathematiker und theoretische Informatiker herumschlagen, scheint gelöst: die Frage, ob die beiden so genannten Komplexitätsklassen P und NP identisch sind oder nicht.

In der Komplexitätstheorie umfasst die Klasse P all die Probleme, die sich mit einer deterministischen Rechenmaschine in einer Rechenzeit t lösen lassen, die von der Größe der Eingangsdaten n höchstens polynomisch abhängt, das heißt t ≤ nk. Als Modell einer deterministischen Rechenmaschine verwenden Theoretiker üblicherweise eine Turing-Maschine, aber auch alle herkömmlichen digitalen Computer gehören dazu. Die Komplexitätsklasse P umfasst also alle Aufgabenstellungen, die sich mit vertretbarer Rechenzeit exakt berechnen lassen.

Das Dokument für die Beweisführung ist hier zu finden (hat "nur" 66 Seiten)
[ Link nur für registrierte Mitglieder sichtbar. Bitte einloggen oder neu registrieren ]

LostPW · 11.08.10, 19:25

auf deutsch wär es ne ecke interessanter^^

Gawan · 11.08.10, 20:20

Ja, weil da hier im Forum eh irgendeiner versteht

Da hast du die falsche Zielgruppe ausgesucht und nein, ich hab keine Lust es euch zu erklären

Tensenmatte · 11.08.10, 21:09

Habe ich es doch gewusst!!!!!!!!!!!!!11111

schranze · 11.08.10, 21:17

Zitat:

Zitat von Gawan

Ja, weil da hier im Forum eh irgendeiner versteht

Da hast du die falsche Zielgruppe ausgesucht und nein, ich hab keine Lust es euch zu erklären

Ich hätte das auch an den Beitrag hängen können.
[ Link nur für registrierte Mitglieder sichtbar. Bitte einloggen oder neu registrieren ]

Die Thematik gehört zur theoretischen Informatik. Also sehr Mathe lastig. Da gibt es Grundkonzepte zu verstehen. Wie z.B.: P, NP oder NPC

RastloseSeele · 11.08.10, 21:27

oh mann.. kann man das irgendwie so formulieren das das bildlich zu verstehen ist oder das man den sinn auch als nicht mathematiker versteht ? ansonsten hilft mir der beitrag etwa so viel wie wenn in afrika nen sack reis umfällt oder ne gans goldene eier ausbrütet..!

würde es gern verstehen.. aber das verständnis hört ja schon bei: komplexitätsklasse auf und was P und NP ist.. damit kann ich erst recht nichts anfangen ^^..! giebts da ne kinderbucherklärung für ?

..!

lg soul.

schranze · 11.08.10, 21:42

Zitat:

Zitat von RastloseSeele

oh mann.. kann man das irgendwie so formulieren das das bildlich zu verstehen ist oder das man den sinn auch als nicht mathematiker versteht ? ansonsten hilft mir der beitrag etwa so viel wie wenn in afrika nen sack reis umfällt oder ne gans goldene eier ausbrütet..!

würde es gern verstehen.. aber das verständnis hört ja schon bei: komplexitätsklasse auf und was P und NP ist.. damit kann ich erst recht nichts anfangen ^^..! giebts da ne kinderbucherklärung für ?

..!

lg soul.

ein sehr bekanntest Beispiel zu der Materie:
[ Link nur für registrierte Mitglieder sichtbar. Bitte einloggen oder neu registrieren ]

RastloseSeele · 12.08.10, 09:38

wenn ich könnte würd ich mich 2x bedanken

..!

also können die chinesen ihre extrem touren jetzt nocht genauer planen ?

*hihi..!

ok konnte jetzt nur den wiki beitrag von dir lesen und nich noch tiefer auf den ersten thread oben eingehen.. muss noch arbeiten ^^..., aber das was ich lesen durfte hat mir schon wieder viel beigebracht .. danke

..! den rest les ich mir wenn ich zeit hab mal in ruhe mit hilfe von wiki durch

..!

schranze · 16.08.10, 14:08

Zitat:

Zitat von RastloseSeele

wenn ich könnte würd ich mich 2x bedanken

..!

also können die chinesen ihre extrem touren jetzt nocht genauer planen ?

*hihi..!

ok konnte jetzt nur den wiki beitrag von dir lesen und nich noch tiefer auf den ersten thread oben eingehen.. muss noch arbeiten ^^..., aber das was ich lesen durfte hat mir schon wieder viel beigebracht .. danke

..! den rest les ich mir wenn ich zeit hab mal in ruhe mit hilfe von wiki durch

..!

Nee Passwörter etc. in ganz große Ungewissheit bringen, wenn jemand raus findet, dass es linearer zeit knackbar ist. Sprich BruteForce war dann mal

Zeodos · 16.08.10, 17:07

Zitat:

Zitat von schranze

Nee Passwörter etc. in ganz große Ungewissheit bringen, wenn jemand raus findet, dass es linearer zeit knackbar ist. Sprich BruteForce war dann mal

was meinst du mit linearer zeit?

rv4 · 16.08.10, 19:58

Ganz vereinfacht könnte man es glaub so formulieren: Es wurde gezeigt, dass schwere Probleme (z.B. mit Passwort mit 200 Sonderzeichen) nicht vlt. doch irgendwie durch nen schlauen Trick entschlüsselt werden können.

Könnte ja sein, dass morgen nen Nordkoreaner drauf kommt, wie man die PW der CIA in 5s knackt. So kann man beruhigt sein, dass es nicht schaffbar ist.

Wobei es meines Wissens nach namenhafte Mathematiker gibt, die an dem Beweis zumindest zweifeln.

Zeodos · 17.08.10, 20:33

ja gut, das war aber glaube ich ohnehin schon allen klar... RSA basiert darauf, dass man große zahlen noch nicht klug und schnell faktorisieren kann... elliptische kurven vertrauen darauf, dass es keinen weg gibt den diskreten logarithmus zu bilden usw...
das das von heute auf morgen wieder ganz anders aussehen kann, ist glaube ich jedem sicherheutsfachmann bekannt..

schranze · 20.08.10, 14:19

Zitat:

Zitat von rv4

Ganz vereinfacht könnte man es glaub so formulieren: Es wurde gezeigt, dass schwere Probleme (z.B. mit Passwort mit 200 Sonderzeichen) nicht vlt. doch irgendwie durch nen schlauen Trick entschlüsselt werden können.

Könnte ja sein, dass morgen nen Nordkoreaner drauf kommt, wie man die PW der CIA in 5s knackt. So kann man beruhigt sein, dass es nicht schaffbar ist.

Wobei es meines Wissens nach namenhafte Mathematiker gibt, die an dem Beweis zumindest zweifeln.

jo ein pwd mit Zeichenlänge von 10 und sagen wir nicht den 200 Sonderzeichen sondern einfach dem Alphabet ohne Groß-Kleinschreibung würde das ergeben

26 hoch 10 Möglichkeiten = 141.167.095.653.376

Der Anstieg der Möglichkeiten ist nicht linear. Sprich wenn die Länge des Passwortes sich um 1 erhöht, dann erhöhen sich nicht linear die Möglichkeiten. Das ist exponentiell.

Hier gut erklärt: [ Link nur für registrierte Mitglieder sichtbar. Bitte einloggen oder neu registrieren ]

Würde der Zeitaufwand nur linear dazu steigen, dann wäre wohl kein PWD sicher

rinserofwinds · 20.08.10, 16:18

Schon jemand [ Link nur für registrierte Mitglieder sichtbar. Bitte einloggen oder neu registrieren ]hier dazu gelesen?

schranze · 23.08.10, 12:18

Zitat:

Zitat von rinserofwinds

Schon jemand [ Link nur für registrierte Mitglieder sichtbar. Bitte einloggen oder neu registrieren ]hier dazu gelesen?

Ja auch gesehen. Das ist der Punkt warum sich die Geister bei der theoretischen Informatik scheiden. Bislang konnte noch keiner einen richtigen Beweis für oder gegen die Vermutung bringen. Es sind nur Annahmen.