---

Geschrieben von Tummel am 17.01.2019 um 19:07:

  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).