NP-Problem deterministisch < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen oder widerlegen Sie:
Zu jedem Problem [mm] T\in [/mm] NP gibt es ein Poylnom p, sodas T durch einen deterministischen Algorithmus mit Zeitkomplexität [mm] O(2^{p(n)}) [/mm] gelöst werden kann, wobei n die Größe der Eingabe bezeichnet. |
Hallo,
ich vermute, dass es stimmt, weil jeder nicht-determ. Turingmaschine in eine determ. umgewandelt werden kann. Jedoch fehlt mir die Idee das zu zeigen.
Da T [mm] \in [/mm] NP ist gibt es ja schon mal ein Polynom p welches die Komplexität der Überprüfung einer Eingabe angibt. T [mm] \in [/mm] NP => eine Eingabe der Länge n kann in O(p(n)) überprüft werden.
Weiter komme ich leider nicht...
Gruß Bernd
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:02 Mi 08.12.2010 | | Autor: | felixf |
Moin Bernd!
> Zeigen oder widerlegen Sie:
> Zu jedem Problem [mm]T\in[/mm] NP gibt es ein Poylnom p, sodas T
> durch einen deterministischen Algorithmus mit
> Zeitkomplexität [mm]O(2^{p(n)})[/mm] gelöst werden kann, wobei n
> die Größe der Eingabe bezeichnet.
> Hallo,
>
> ich vermute, dass es stimmt, weil jeder nicht-determ.
> Turingmaschine in eine determ. umgewandelt werden kann.
> Jedoch fehlt mir die Idee das zu zeigen.
> Da T [mm]\in[/mm] NP ist gibt es ja schon mal ein Polynom p welches
> die Komplexität der Überprüfung einer Eingabe angibt. T
> [mm]\in[/mm] NP => eine Eingabe der Länge n kann in O(p(n))
> überprüft werden.
> Weiter komme ich leider nicht...
Weisst du, was ein NP-vollstaendiges Problem ist?
Jedes Problem aus NP kann mit polynomiellen Aufwand auf jedes NP-vollstaendige Problem zurueckgefuehrt werden.
Wenn du dies weisst und dir ein einfaches NP-vollstaendiges Problem herauspickst, kannst du die Aufgabe loesen.
LG Felix
|
|
|
| |
|
Hi Felix,
nach unserer Definition, weiß ich, dass jedes NP-vollständige Problem durch polynom. Transformation in jedes andere NP-vollständige Problem reduziert werden kann.
Dass es von NP-Probleme geht, wusst ich nicht.
Aber ich sehe grad nicht, wie mir die Reduktion auf NP-vollständig Probleme weiter helfen soll, denn von denen weiß ich auch nicht mit Sicherheit, ob sie polynomiell gelöst werden können oder nicht, man vermutet doch nu,r dass man sie polynomiell nicht lösen kann.
LG Bernd
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:41 So 12.12.2010 | | Autor: | felixf |
Moin Bernd,
> nach unserer Definition, weiß ich, dass jedes
> NP-vollständige Problem durch polynom. Transformation in
> jedes andere NP-vollständige Problem reduziert werden
> kann.
> Dass es von NP-Probleme geht, wusst ich nicht.
das ist doch gerade die ![[]](/images/popup.gif) Definition von NP-vollstaendigen Problemen, dass man alle Probleme aus NP auf sie reduzieren kann!
> Aber ich sehe grad nicht, wie mir die Reduktion auf
> NP-vollständig Probleme weiter helfen soll, denn von denen
> weiß ich auch nicht mit Sicherheit, ob sie polynomiell
> gelöst werden können oder nicht, man vermutet doch nu,r
> dass man sie polynomiell nicht lösen kann.
Natuerlich kann man sie nicht einfach polynomiell loesen; ansonsten wuerdest du P = NP beweisen.
Es reicht doch zu wissen:
* Dein Probem laesst sich in polynomieller Zeit auf ein beliebiges, von dir gewaehltes NP-vollstaendiges Problem reduzieren. Sagen wir die Laufzeit ist [mm] $p_1(n)$, [/mm] wobei $n$ die Eingabegroesse ist.
* Dein fest gewaehltes NP-vollstaendiges Problem kannst du in [mm] $2^{p_2(n)}$ [/mm] Schritten loesen, wobei [mm] $p_2(n)$ [/mm] ein Polynom ist. Um SAT zu loesen, brauchst du etwa [mm] $O(2^{n + \varepsilon})$ [/mm] Schritte (fuer jedes [mm] $\varepsilon [/mm] > 0$), falls du einen Ausdruck in $n$ Variablen hast.
Wenn du beides kombinierst, bekommst du eine Laufzeit der Form [mm] $(2^{p(n)})$ [/mm] (beachte, dass etwa [mm] $O(p_1(n)) [/mm] = [mm] O(2^{\log n \cdot \deg p_1} \subsetneqq O(2^n)$ [/mm] ist).
LG Felix
|
|
|
| |
|
Hey,
ok der 1. Punkt ist klar.
Zum 2.:
Das man ein NPC-Problem in O( [mm] 2^{p_2(n)} [/mm] )lösen kann verstehe ich noch, weil man die nicht deterministischen [mm] \epsilon [/mm] -Übergänge mit der Potenzmengekonstruktion wegkriegt.
(Neben bei : kann ich sagen das die Laufzeit eines Automaten in O(Knotenanzahl) ist? oder wie kommt man auf die [mm] 2^{p_2(n)} [/mm] )
Jedoch hat das Polynom [mm] p_2 [/mm] nicht mit dem Polynom [mm] p_1 [/mm] zu tun,oder?Die Laufzeit der Reduktion hat nichts mit der Laufzeit des Lösens des NPC Problems zu tun?
>(beachte, dass etwa [mm] $O(p_1(n)) [/mm] = [mm] O(2^{\log n \cdot \deg p_1} \subsetneqq >O(2^n)$ [/mm] ist)
Den Hinweis verstehe ich nicht ganz? Was ist [mm] \deg p_1 [/mm] ?
Gruß Bernd
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Sa 18.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
