Theoret. Inform.: Sinn von NTM, NP-Vollständigkeit, <= ?
Martin Horoba
ich kann trotz ausführlichem Lesen in einigen Büchern den Sinn von NTM
(nichtdeterm. Turing Maschinen) und der Klasse NP (Klasse der in
polynomieller Zeit von NTM lösbaren Probleme) nicht verstehen /
finden.
Auch fehlt mir das Verständnis, warum der Begriff "Reduktion" für zB
die Sprachen A <= B (und dazu noch die Relation <=) gewählt wurde.
Danke für Hilfen,
Martin Horoba, Dortmund
Björn Krüger
> ich kann trotz ausführlichem Lesen in einigen Büchern den Sinn von NTM
> (nichtdeterm. Turing Maschinen) und der Klasse NP (Klasse der in
> polynomieller Zeit von NTM lösbaren Probleme) nicht verstehen /
> finden.
Hallo,
die Klasse NP sind Probleme die nicht in Polynomieller Zeit von
deterministischen TMs geloest werden koennen.
Eine NTM schafft das, indem sie die richtige Loesung raet und dann zur
Loesung bzw. zum halten kommt.
> Auch fehlt mir das Verständnis, warum der Begriff "Reduktion" für zB
> die Sprachen A <= B (und dazu noch die Relation <=) gewählt wurde.
Eine Sprache wird reduziert, da sie in die andere umwandelt wird. Ist
die eine entscheidbar, dann ist es auch die andere. Das schwere ist
diesen uebergang zu zeigen. Man zeigt im Endefekt das sie gleich schwer
zu entscheiden sind.
Gruss
Bjoern
--
-----------------------------------------------------------
| Björn Krüger | Tel.: +49(0)228/2808636 |
| Endenicher Allee 17 / 3321 | D2 : +49(0)172/2746540 |
| 53115 Bonn | E-Mail: krue...@bonn.edu |
-----------------------------------------------------------
Peter Wernerus
> die Klasse NP sind Probleme die nicht in Polynomieller Zeit von
> deterministischen TMs geloest werden koennen.
Falsch. Die Klasse NP ist die Klasse der Probleme, die in polynomieller
Zeit von nichtdterminstischen TMs gelöst werden kann. Da aber jede
deterministische TM auch eine nichtdeterministische TM ist, kannst du
auch jedes Problem, das du deterministisch in Polynomialzeit lösen
kannst nichtdeterministisch in Polynomialzeit lösen. => Problem die in
polynomieller Zeit von DTM zu lösen sind sind in NP. Oder anders
ausgedrückt: P ist Teilmenge von NP. Was zu beiweisen ist, ist noch die
Tatsache das P echte Teilmenge von NP ist.
> Eine NTM schafft das, indem sie die richtige Loesung raet und dann zur
> Loesung bzw. zum halten kommt.
Ungenau. Es existieren Probleme, die von NTM so gelöst werden können.
Dass diese Problem aber nicht von DTM in Polynomialzeit lösbar sind, ist
bislang unbewiesen.
>>Auch fehlt mir das Verständnis, warum der Begriff "Reduktion" für zB
>>die Sprachen A <= B (und dazu noch die Relation <=) gewählt wurde.
>
>
> Eine Sprache wird reduziert, da sie in die andere umwandelt wird. Ist
> die eine entscheidbar, dann ist es auch die andere. Das schwere ist
> diesen uebergang zu zeigen. Man zeigt im Endefekt das sie gleich schwer
> zu entscheiden sind.
Nein, man zeigt, dass eine Sprache mindestens so schwer ist wie die
andere. Will man zeigen, dass sie gleich schwer sind, so muß man sowohl
A auf B, als auch B auf A reduzieren.
Grüsse,
Peter Wernerus
Björn Krüger
> Björn Krüger wrote:
> > die Klasse NP sind Probleme die nicht in Polynomieller Zeit von
> > deterministischen TMs geloest werden koennen.
> Falsch. Die Klasse NP ist die Klasse der Probleme, die in polynomieller
> Zeit von nichtdterminstischen TMs gelöst werden kann. Da aber jede
> deterministische TM auch eine nichtdeterministische TM ist, kannst du
> auch jedes Problem, das du deterministisch in Polynomialzeit lösen
> kannst nichtdeterministisch in Polynomialzeit lösen. => Problem die in
> polynomieller Zeit von DTM zu lösen sind sind in NP. Oder anders
> ausgedrückt: P ist Teilmenge von NP. Was zu beiweisen ist, ist noch die
> Tatsache das P echte Teilmenge von NP ist.
Hallo, Danke fuer die Korrektur, ich hatte das irgendwie genau falsch
herum verstanden.
> >>Auch fehlt mir das Verständnis, warum der Begriff "Reduktion" für zB
> >>die Sprachen A <= B (und dazu noch die Relation <=) gewählt wurde.
> >
> > Eine Sprache wird reduziert, da sie in die andere umwandelt wird. Ist
> > die eine entscheidbar, dann ist es auch die andere. Das schwere ist
> > diesen uebergang zu zeigen. Man zeigt im Endefekt das sie gleich schwer
> > zu entscheiden sind.
>
> Nein, man zeigt, dass eine Sprache mindestens so schwer ist wie die
> andere. Will man zeigen, dass sie gleich schwer sind, so muß man sowohl
> A auf B, als auch B auf A reduzieren.
OK, aber wie zeigst Du das die Sprachen glecih schwer sind? Nicht indem
die eine in die andere umgewandelt wird?
Gruss
Björn
Peter Wernerus
>>Nein, man zeigt, dass eine Sprache mindestens so schwer ist wie die
>>andere. Will man zeigen, dass sie gleich schwer sind, so muß man sowohl
>>A auf B, als auch B auf A reduzieren.
>
>
> OK, aber wie zeigst Du das die Sprachen glecih schwer sind? Nicht indem
> die eine in die andere umgewandelt wird?
Der Begriff Sprachen umwandeln ist auch etwas ungenau. Im Prinzip geht
es bei Reduktion darum, das man ein Problem A unter Verwendung des
Problems B lösen kann. Dann folgt: Kann man B berechnen, so kann man
auch A berechnen. Anhand der Komplexität der Umwandlung von B nach A
kann man auch ermitteln wie die Komplexität des Problems höchstens ist.
Dieses Problem können natürlich auch Akzeptanz von Sprachen sein. Wenn
du das in beiden Richtungen machst, beweist du damit natürlich auch,
dass sie gleich schwer sind. Denn wenn du zeigst, dass A schwerer oder
gleichschwer B ist und B schwerer oder gleichschwer A ist, dann sind A
und B selbstverständlich gleichschwer.
Eine andere Möglichkeit ist es, einfach zu zeigen, in welcher Klasse
(welcher Chomaky Typ) eine Sprache ist. Sind sie vom gleichen Typ, sind
sie gleich schwer.
Es mag sein, dass es noch andere Möglichkeiten gibt. Das Ganze ist
leider schon ein bisschen her.
Grüsse,
Peter Wernerus
Peter Kämmerling
> (welcher Chomaky Typ) eine Sprache ist. Sind sie vom gleichen Typ, sind
Chomsky (-> Noam Chomsky)
Peter
Peter Wernerus
Tja, das a liegt halt direkt neben s. Kann schon mal passieren, dass man
sich da vertippt. Ja, es muß Chomsky heißen.
Grüße,
Peter Wernerus