PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Beweis: P!=NP


AlSvartr
2007-01-02, 18:17:35
Wer hat es nicht schon einmal erlebt: Es passiert. Es passiert von einem Moment auf den anderen - und zwar, ohne dass irgendjemand darauf vorbereitet gewesen wäre. Von einem selbst ganz zu schweigen. Ob es jetzt um Ratten geht, die auf den Hinterbeinen laufend Bridge spielen und sich dann doch nur als beliebig Karten-durch-die-Gegend-werfende Kanalisationsbewoher herausstellen oder vielleicht doch eher um die kommunikative Problematik, die immer wieder be- oder auch entsteht, wenn man versucht, es zu tun.

Versucht, was zu tun?

Lässt sich ein Sachverhalt, der n>=2 Individuen involviert, automatisch hierarchisieren, indem man vielleicht bestimmten Aspekten geringere Prioritäten zuteilt? Welche Aspekte wären das dann? Und wann würde die Idee versagen? Vermutlich könnte sie nicht das grundlegende Problem verhindern: Das schlechte Gefühl, was anfänglich entsteht, wenn man nichts über die niedriger (oder höher) priorisierten Dinge weiß. Wer sieht sich schon selbst gern als Teil eines ganzen Baums? Wer möchte eine größere Anzahl gleichberechtigter Brüder? Wer ist sich nicht zuerst einmal selbst der Nächste?

Hat das Ding aber erst einmal Wurzeln geschlagen, lässt sich nicht mehr viel daran ändern. Und einfach fällen kann man es auch nicht, das verfluchte Biest. Sein Durchmesser reicht von hier bis sonstwohin. Sonstwo. Da, wo die hart arbeitenden Menschen das Geschirr mit den kleinen Bläschen herstellen. Wen interessieren die schon? Wen interessiert schon das Geschirr?

Problematisch.

hadez16
2007-01-02, 18:43:41
fragen wir chuck norris dazu

Oberon
2007-01-02, 18:45:54
Egal was du genommen hast: Ich will es auch :O













scnr

kasir
2007-01-02, 18:46:38
ich versteh den inhalt des textes nicht o_O. mir würde es reichen ,wenn mich jmd. über P!=NP aufklärt. welche bedeutung hat P!=NP?

edit: gibt es überhaupt etwas zu verstehen?

AlSvartr
2007-01-02, 18:49:24
ich versteh den inhalt des textes nicht o_O. mir würde es reichen ,wenn mich jmd. über P!=NP aufklärt. welche bedeutung hat P!=NP?

Es wäre jedenfalls schöner für die Kryptographie, als P==NP. Es sei denn man wird zum Quantenkasper. Dann ist es auch wieder Wurst. Hm, lecker.

edit: gibt es überhaupt etwas zu verstehen?
Das ist Dir überlassen.

Crack
2007-01-02, 18:50:27
ich denk mal er meint P=NP! wie es auf der homepage seiner sig steht.
aber ich versteh nur bahnhof

sei laut
2007-01-02, 18:51:10
P! = 1*2*3*4*5 - unendlich
N*P = 5 x 3 oder 5 x 7

Und er will wissen, ob P! irgendwann mal N*P ist, also den gleichen Wert hat.

Jedenfalls sagt mir das mein geringes mathematisches Wissen. X-D

Senior Sanchez
2007-01-02, 18:54:34
@seiLaut

LOOOL

Ich kapiere den Sinn des Threads jetzt spontan nicht, aber P == NP bzw. P != NP behandelt die Frage, ob die Menge der Probleme die durch eine deterministische Turingmaschine in Polynomialzeit gelöst werden können gleich der Menge der Probleme entspricht, die eine nichtdeterministische Turingmaschine in Polynomialzeit löst.

dcAlge
2007-01-02, 18:59:10
Und ich hab mich jetzt auf nen tollen Beweis gefreut, dass P!=NP ist und dann kommt da sonen Schmarn. ^^ Naja... Dann muss ich wohl weiter den Traveling Salesman spielen.... MfG, dcalge

AlSvartr
2007-01-02, 19:10:07
ich denk mal er meint P=NP! wie es auf der homepage seiner sig steht.
aber ich versteh nur bahnhof
Ich meinte es schon so, wie es im Titel steht. Schließlich soll man sich ja immer alle Möglichkeiten offenhalten. Mehrgleisig fahren. Am Ende wird man sehen, was die bessere (nicht: richtigere) Entscheidung gewesen wäre. Effektiver. Produktiver. Offensiver.

Und ich hab mich jetzt auf nen tollen Beweis gefreut, dass P!=NP ist und dann kommt da sonen Schmarn. ^^
Das hast Du doch nicht wirklich geglaubt. Trotzdem ist das mit dem Schmarrn gemein.

Senior Sanchez
2007-01-02, 19:52:59
Ich hatte eigentlich auch gedacht, dass hier ein Beweis kommt, weil der Thread im Offtopic war und nicht auf der Spülwiese. Wäre er dort gewesen, hätte ich mir das gleich denken können.

Jenny23
2007-01-02, 20:02:50
Die gestörtesten Leute werden Mathematiker. Jene unter diesen, die doch noch einen Freund fanden, nennen sich Informatiker.

Und die anderen sind neidisch, weil sie nie ein Wort von all diesen abstrakten Konstruktionen verstehen. :(

Ich weiss zwar was eine Turingmaschine ist (glaube ich zumindest), aber der Rest erschließt sich mir nicht. Wie kann es eine nicht deterministische Turingmaschine geben?

hadez16
2007-01-02, 20:09:37
Ich weiss zwar was eine Turingmaschine ist (glaube ich zumindest), aber der Rest erschließt sich mir nicht. Wie kann es eine nicht deterministische Turingmaschine geben?

das ist glaub ich, wenn bei der grammatik auf beiden seiten nicht-terminalobjekte stehen können

ODER

rofl

AlSvartr
2007-01-02, 20:23:39
Ich weiss zwar was eine Turingmaschine ist (glaube ich zumindest), aber der Rest erschließt sich mir nicht. Wie kann es eine nicht deterministische Turingmaschine geben?
Der Nichtdeterminismus entsteht, wenn für eine Eingabe mehrere Zustandsübergänge definiert sind. Dann befindet sich die Maschine prinzipiell zeitgleich in mehreren Zuständen. Gibts auch schon bei einfachen endlichen Automaten. Aber da ist man sich ob der Äquivalenz im Klaren :wink:

Botcruscher
2007-01-02, 20:30:22
Für N=1 stimmt die Aussage nicht.:|

PS: Für den Fall das ich irgendwie verstanden hab was er meint.:biggrin:

Senior Sanchez
2007-01-02, 20:57:15
Ums mal ganz einfach zu sagen:

Eine Turingmaschine ist in dem Sinne ein Gedankenkonstrukt (obwohl jeder Computer ansich eine Turingmaschine ist), dass es erlaubt jede (trivial) berechenbare Funktion berechnen zu können. Sei es nun die Summe zweier Zahlen, die Höhe der Mehrwertsteuer eines Produkts oder auch ganz komplexe Sachen wie 3D-Grafiken (die sich ja wieder auf einfache Funktionen abbilden lassen). Alles was ein Mensch theoretisch berechnen kann, kann auch eine Turingmaschine berechnen.

Eine deterministische Turingmaschine ist in dem Sinne eine Turingmaschine die eine Eingabe (z.B. den Preis eines Produkts) erhält und daraus in einen eindeutig bestimmbaren Zustand übergeht und mir ein Ergebnis liefert, welches durch diesen Zustand repräsentiert wird. Es ist quasi vorhersagbar in welchen Zustand sie bei einer bestimmten Eingabe übergeht. (Wenn ich 19% Mehrwertsteuer von 100 € brutto berechnen muss, ist klar dass da am Ende als einzige Lösung 119 € rauskommt)

Bei einer nicht-deterministischen Turingmaschine ist das nicht der Fall: Sie kann in mehrere verschiedene Folgezustände übergehen, genauer gesagt errät sie immer den richtigen Folgezustand.

Man merkt schon, dass die nicht-deterministische Turingmaschine etwas abgefahren klingt und in der Tat existiert sie (bisher) nur in der Theorie, aber nicht in der Praxis.

Um jetzt den Bogen zu P vs. NP zu spannen: P ist die Menge aller Probleme die in polynomialer Zeit von einer deterministischen Turingmaschine berechnet werden kann, sprich dass die Dauer zur Berechnung des Problems eine Polynomfunktion in Abhängigkeit der Größe der Eingabemenge darstellt. Bekomme ich zum Beispiel 5 Zahlen und eine Turingmaschine soll diese sortieren, die dafür n² Schritte braucht - also 5*5 Schritte also, so erledigt sie diese Aufgabe in polynomialer Zeit, da n² eine Polynomfunktion ist.

Das gleiche eben mit der NP Sache, nur dass dafür eine nicht-deterministische Turingmaschine vorausgesetzt wird.

Es gibt nun Probleme, die nach bisherigem Kenntnisstand nur in NP liegen, sprich nur eine nicht-deterministische Turingmaschine kann hier eine Lösung in Polynomialzeit finden. Die Frage die die ganze Welt, okay nicht die ganze Welt ;), beschäftigt ist: Lässt sich für jedes Problem in NP eine äquivalente Lösung in P finden?

Bisher wurde das noch nicht bewiesen...

Jenny23
2007-01-02, 22:58:55
Kann es sein, daß man die nicht-deterministische Turingmaschine auch Quantencomputer nennt?

Quantar
2007-01-02, 23:04:13
Kann es sein, daß man die nicht-deterministische Turingmaschine auch Quantencomputer nennt?
DIE Frage stellte sich mir auch gerade :usad:

PatkIllA
2007-01-02, 23:13:21
Kann es sein, daß man die nicht-deterministische Turingmaschine auch Quantencomputer nennt?Nicht wirklich.
Ein Quantencomputer kann zwar einige Dinge in polynomieller Zeit berechnen, für die ein herkömmlicher Computer exponentielle Zeit benötigt, aber das Konstrukt ist doch ganz anders.
Du nennst einen herkömmlichen Rechner doch auch nicht Turingmaschine, auch wenn sie sich gegenseitig "emulieren" können.

AlSvartr
2007-01-02, 23:14:38
Nein, kann es nicht. Im Quantencomputing gibt es wieder weitere ganz eigene Komplexitätsklassen (sowas wie QNP gibts glaube ich auch (ob der Name stimmt, weiß ich nicht ;)), ich weiß allerdings nicht, wie es mit sowas wie einer Äquivalenz zwischen "QP" und "QNP" aussieht..ich kann ja mal fragen, wenn ich den Kollegen wieder spreche :D). Besagter Kollege beschäftigt sich im Rahmen seines Masterstudiums mit Quantenkryptographie, da hat er mit solchen Schweinereien auch ne Menge zu tun :S

<edit>Ok, NP heißt dort NQP :S