Was wäre wenn NP=P < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen Sie: P=NP => [mm] P\setminus\{ \emptyset , \Sigma^{*}\} [/mm] = NPC.
Warum sind [mm] \emptyset [/mm] und [mm] \Sigma^{*} [/mm] (insbesondere unter dieser Annahme) nicht NP-vollständig? |
Hey,
puuuu...komplett überfragt.
Wieso ist [mm] \emptyset [/mm] bzw. [mm] \Sigma^{*} [/mm] nicht in NPC? D.h. doch, dass es nicht möglich ist NPC- Probleme auf sie zu reduzieren, denn in NP sind sie ja.
Was ist überhaupt das Problem [mm] \emptyset? [/mm] Da wird nicht eingegeben; heißt es es ist immer gelöst, wenn nicht eingegeben wird?
Gruß Snafu
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:47 So 12.12.2010 | | Autor: | felixf |
Moin Snafu,
> Zeigen Sie: P=NP => [mm]P\setminus\{ \emptyset , \Sigma^{*}\}[/mm] =
> NPC.
> Warum sind [mm]\emptyset[/mm] und [mm]\Sigma^{*}[/mm] (insbesondere unter
> dieser Annahme) nicht NP-vollständig?
> Hey,
>
> puuuu...komplett überfragt.
> Wieso ist [mm]\emptyset[/mm] bzw. [mm]\Sigma^{*}[/mm] nicht in NPC? D.h.
> doch, dass es nicht möglich ist NPC- Probleme auf sie zu
> reduzieren, denn in NP sind sie ja.
Exakt.
> Was ist überhaupt das Problem [mm]\emptyset?[/mm] Da wird nicht
> eingegeben; heißt es es ist immer gelöst, wenn nicht
> eingegeben wird?
Das sind Sprachen. [mm] $\emptyset$ [/mm] ist die leere Sprache, [mm] $\Sigma^\ast$ [/mm] die "Allsprache".
Das Problem ist, dass das Entscheidungsproblem $w [mm] \in \emptyset$ [/mm] bzw. $w [mm] \in \Sigma^\ast$ [/mm] immer die gleiche Antwort hat. Du kannst also ein beliebiges anderes Entscheidungsproblem $w [mm] \in [/mm] L$ nicht in polynomieller Zeit auf $w' [mm] \in \emptyset$ [/mm] bzw. $w' [mm] \in \Sigma^\ast$ [/mm] zurueckfuehren, da dies nicht das zurueckliefert, was du fuer $w [mm] \in [/mm] L$ brauchst (entweder liefert es immer "ja" oder immer "nein" zurueck, jedoch haengt $w [mm] \in [/mm] L$ von $w$ ab, wenn $L [mm] \neq \emptyset, \Sigma^\ast$ [/mm] ist).
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:12 Mo 13.12.2010 | | Autor: | SnafuBernd |
Hey,
ja das klingt logisch.Danke.
Snafu
|
|
|
|
