Wortproblem Typ 1 ist NP-schwer kann ma es per Turing Maschine berechnen?
Das Wortproblem Typ 1 für kontextsensitive Sprachen ist entscheidbar.
Bzgl. der Komplexität ist es NP-schwierig.
O(k^n) Komplexität
Laut der Folie kann man nicht zeigen, dass es in NP liegt. Es ist NP-schwierig.
Nun meine Frage: Ist das Wortproblem Typ 1 Turing-Maschinen berechenbar? Ja oder Nein, wenn es wie hier angegeben NP-schwierig ist?
Es gilt P Teilmenge von NP.
2 Antworten
Es ist entscheidbar, also gibt es eine DTM, welche die Sprache entscheidet (jedes Wort akzeptiert oder ablehnt). Berechnen lässt sich die Sprache somit auch (alle Wörter des Alphabets durchgehen und wenn in Sprache, dann aufs Band schreiben). Dies geht nur wahrscheinlich nicht in poly-Zeit, deshalb ist es NP-schwer.
Wenn du eine Tabelle hättest wo als Überschriften angegeben sind
P NP NP-vollständing und TuringMaschinenberechenbar.
Nun muss man Kreuze setzen, wo würdest du nun das WortProblem Typ 1 einstufen, wenn gilt P Ungleich NP?
Hätte ich auch gesagt. Bei NP verunsichert mich gerade, dass bei mir in den Unterlagen NP-vollst. steht
Ich gehe dem mal kurz noch nach.
So, also es sollte nicht in NP liegen und damit auch nicht NP-vollst. sein.
Wie schaut es mit 2-SAT aus? Wo würdest du dies einstufen bei
P NP NP-vollständing und TuringMaschinenberechenbar.
2-SAT ist in P und somit auch in NP. Berechenbar ist es somit auch.
NP-vollständig ist es nicht. Sonst würde direkt P=NP folgen.
Da bin ich gerade gar nicht drinnen. Aber das muss ja irgendwie mit Reduktion gehen.
Du baust einen Algorithmus, der ein NP-Problem löst indem er auf eine TM zurückgreift, die entscheidet, ob ein Wort in einer kontextsensitiven Sprache liegt.
Und entscheidbar wird es wahrscheinlich sein, da du im Zweifelsfalle alle Kombinationen durchprobieren kannst oder soetwas.
Ich würde es dann nur in TuringMaschinenberechenbar einstufen, da man nicht zeigen kann, dass es in NP liegt.