P und NP (3) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 12:59 Mi 08.02.2006 | | Autor: | mathiash |
| Aufgabe | Es sei [mm] L\subseteq\{0,1\}^{\star}.
[/mm]
Zeige, dass folgende Aussagen äquivalent sind:
(1) [mm] L\in [/mm] NP, d.h. es gibt eine polynomiell zeitbeschränkte NTM M mit
L(M)=L.
(2) Es gibt eine polynomiell balancierte Relation [mm] R\subseteq\{0,1\}^{\star}\times\{0,1\}^{\star} [/mm] mit [mm] R\in [/mm] P (d.h. es gibt einen deterministischen polyzeit-Algorithmus A, der bei Eingabe (x,y) ausgibt, ob [mm] (x,y)\in [/mm] R
oder nicht), so dass
[mm] L=\{x\in\{0,1\}^{\star}|\exists y\in\{0,1\}^{\star}\:\: s.d.\:\: (x,y)\in R\}
[/mm]
Dabei heisst R polynomiell balanciert genau dann, wenn es ein Polynom p(n) gibt mit
[mm] \forall (x,y)\in\{0,1\}^{\star}\times\{0,1\}^{\star}\:\: (\: (x,y)\in R\:\rightarrow\: |y|\leq p(|x|)\:\: [/mm] ) |
Hallo zusammen,
das ist sozusagen absolute Grundlage, seht es als Warming Up.
Gruss,
Mathias
|
|
|
