Klasse NP < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Zusammen,
Ich würde gerne wissen, ob ich folgende Definition richtig verstehe:
Zitat:
"Eine Sprache [mm]L \in \mathcal{NP}[/mm], wenn es eine in polynomieller Zeit arbeitende Turing Maschine [mm]M(\cdot{},\cdot{})[/mm] und ein Polynom [mm]p[/mm] gibt, so daß [mm]\forall x\in\{0,1\}^{\star}[/mm] gilt:
[mm]\bullet[/mm] Ist [mm]x \in L[/mm], so [mm]\exists y \in \{0,1\}^{\star}[/mm] mit [mm]\operatorname{length}(y) \le p(\operatorname{length}(x))[/mm], so daß [mm]M(x,y)[/mm] akzeptiert.
[mm]\bullet[/mm] Ist [mm]x \notin L[/mm], so gilt [mm]\forall y \in \{0,1\}^{\star}[/mm] mit [mm]\operatorname{length}(y) \le p(\operatorname{length}(x))[/mm], daß [mm]M(x,y)[/mm] die Eingabe verwirft.
Ich habe versucht, daß anhand einer kleinen Übungsaufgabe zu verstehen. Gegeben ist die Sprache [mm]L[/mm] aller Primzahlen, und man soll zeigen, daß [mm]L \in \mathcal{NP}[/mm] ist. Ich dachte mir nun, daß man jede Primzahl ausschließlich durch Einsen kodieren könnte, also so:
[mm]L := \{11,111,11111,\dotsc\}[/mm]
Und [mm]M[/mm] würde dann ausschließlich Eingaben für [mm]x[/mm] akzeptieren, die nur aus Einsen bestehen und für die es ein entsprechendes [mm]y[/mm] gibt. Und das [mm]y[/mm] würde dann z.B. für [mm]n = 5[/mm] so aussehen:
[mm]1011011101111011111[/mm]
[mm]M[/mm] würde dann die Eingabe [mm]x[/mm] nacheinander durch 1, 11, u.s.w. teilen, wobei die Nullen als Trennzeichen dienen sollen. War mindestens eine ganzzahlige Divisionen neben der Ersten und Letzten ohne Rest, so ist [mm]x[/mm] keine Primzahl und wird nicht akzeptiert, bestand [mm]x[/mm] nicht nur aus Einsen wird es auch verworfen. Wie lang ist nun ein [mm]y[/mm] für ein gegebenes [mm]x[/mm]? Es besteht aus [mm]\operatorname{length}x-1[/mm] Nullen und [mm]\tfrac{\operatorname{length}x(\operatorname{length}x+1)}{2}[/mm] Einsen. Es gilt also:
[mm]\operatorname{length}(y) \le 0.5\operatorname{length}^2x + 1.5\operatorname{length}x - 1 =: p(\operatorname{length}x)[/mm]
Also wenn es nun ein solches [mm]M[/mm] gibt(, das man auch durch falsche Zertifikate wie 1110111 oder 000 nicht "austricksen" kann ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]") ), dann ist [mm]L\in\mathcal{NP}[/mm], richtig?
Danke für die Hilfe!
Viele Grüße
Karl
|
|
| |
|
Hallo und guten Morgen Karl,
Du hast hier die Primzahlen unär codiert, das ist gelinde gesagt mit Vorsicht zu geniessen, denn der Komplexitätsstatus hängt wesentlich von der
genauen Codierung ab. Für Deine Sprache L der Unärcodierungen von Primzahlen ist es leicht einzusehen, dass sie sogar in P ist.
Wenn Du jedoch Primzahlen binár anstatt unär codierst, so hat also die Codierung von [mm] p\in\N [/mm]
die Länge [mm] O(\log [/mm] p) anstatt O(p), und d.h. Du kannst nicht einfach durch Teilbarkeitstest mit allen n<p in Polynomzeit sehen, ob p prim ist (es gibt
dann nämlich [mm] \Theta (p)=\Theta (2^{\log (p)}) [/mm] viele solche, also exponentiell in der Codierungslänge von p viele.
Für die Sprache L' der Binärcodierungen von Primzahlen gilt trotzdem [mm] L'\in [/mm] NP, und es gilt sogar [mm] L'\in [/mm] P, aber das wollen wir hier jetzt nicht besprechen,
nicht wahr ?
[mm] L'\in [/mm] NP zeigt man mit einem kleinen zahlentheoretischen Argument, das sehr gut im Buch Computational Complexity von Christos Papadimitriou
beschrieben ist, ich werd es später noch hier in den Strang setzen.
Deine allgemeine Charakterisierung von NP sieht man wie folgt ein:
Wenn in NP, gibt es ja eine Polyzeit-NTM M für L, und dann kannst Du eine deterministische Polyzeit-Maschine [mm] M_2
[/mm]
für L entwerfen, die zu gegebener Eingabe x und String y testet, ob y eine akzeptierende Berechnung von M auf Eingabe x codiert.
Gruss,
Mathias
|
|
|
|
