|
|
|
11.08.10, 15:29
|
#1
|
Partygirl
Registriert seit: Oct 2008
Beiträge: 92
Bedankt: 103
|
P != NP sehr wahrscheinlich bewiesen!
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 ]
__________________
************/2ulzejk
|
|
|
11.08.10, 19:25
|
#2
|
Newbie
Registriert seit: Nov 2009
Beiträge: 58
Bedankt: 385
|
auf deutsch wär es ne ecke interessanter^^
|
|
|
11.08.10, 20:20
|
#3
|
Banned
Registriert seit: Jan 2009
Beiträge: 21
Bedankt: 27
|
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
|
|
|
11.08.10, 21:09
|
#4
|
Anfänger
Registriert seit: Oct 2009
Beiträge: 22
Bedankt: 10
|
Habe ich es doch gewusst!!!!!!!!!!!!!11111
|
|
|
11.08.10, 21:17
|
#5
|
Partygirl
Registriert seit: Oct 2008
Beiträge: 92
Bedankt: 103
|
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
__________________
************/2ulzejk
|
|
|
11.08.10, 21:27
|
#6
|
Erfahrenes Mitglied
Registriert seit: Sep 2009
Beiträge: 645
Bedankt: 726
|
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.
|
|
|
11.08.10, 21:42
|
#7
|
Partygirl
Registriert seit: Oct 2008
Beiträge: 92
Bedankt: 103
|
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 ]
__________________
************/2ulzejk
|
|
|
12.08.10, 09:38
|
#8
|
Erfahrenes Mitglied
Registriert seit: Sep 2009
Beiträge: 645
Bedankt: 726
|
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 ..!
|
|
|
16.08.10, 14:08
|
#9
|
Partygirl
Registriert seit: Oct 2008
Beiträge: 92
Bedankt: 103
|
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
__________________
************/2ulzejk
|
|
|
16.08.10, 17:07
|
#10
|
Mitglied
Registriert seit: May 2010
Beiträge: 427
Bedankt: 224
|
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?
|
|
|
16.08.10, 19:58
|
#11
|
Anfänger
Registriert seit: Sep 2009
Beiträge: 20
Bedankt: 13
|
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.
|
|
|
17.08.10, 20:33
|
#12
|
Mitglied
Registriert seit: May 2010
Beiträge: 427
Bedankt: 224
|
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..
|
|
|
20.08.10, 14:19
|
#13
|
Partygirl
Registriert seit: Oct 2008
Beiträge: 92
Bedankt: 103
|
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
__________________
************/2ulzejk
|
|
|
20.08.10, 16:18
|
#14
|
Banned
Registriert seit: Sep 2008
Beiträge: 750
Bedankt: 937
|
Schon jemand [ Link nur für registrierte Mitglieder sichtbar. Bitte einloggen oder neu registrieren ]hier dazu gelesen?
|
|
|
23.08.10, 12:18
|
#15
|
Partygirl
Registriert seit: Oct 2008
Beiträge: 92
Bedankt: 103
|
Zitat:
Zitat von rinserofwinds
|
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.
__________________
************/2ulzejk
|
|
|
Themen-Optionen |
|
Ansicht |
Linear-Darstellung
|
Forumregeln
|
Du kannst keine neue Themen eröffnen
Du kannst keine Antworten verfassen
Du kannst keine Anhänge posten
Du kannst nicht deine Beiträge editieren
HTML-Code ist Aus.
|
|
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 04:19 Uhr.
().
|