Entscheidbar ob Sprachen einer Komplexitätsklasse angehören?
Meine Frage:
Welche der folgenden Sprachen sind entscheidbar, welche nicht? Begründen Sie Ihre Antworten. ¨
a) { G | G ist eine Grammatik und L(G) element P}
b) { G | G ist eine kontextfreie Grammatik und L(G) element NP}
( G kodiert/gödelisiert)
Meine Ideen:
Eine Verständnisfrage - bin dankbar für jeden Hinweis.
Vielleicht nein für a) ? Die Sprachfamilie der Komplexitätsklasse P ist eine Teilmenge der Sprachfamilie der Komplexitätsklasse NP, doch ist deren Verhältnis zueinander ja ungeklärt (P-NP-Problem).
