Entscheidbar ob Sprachen einer Komplexitätsklasse angehören? |
| 17.01.2019, 19:07 | Auf diesen Beitrag antworten » |
| Tummel | 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). |
|
|
|
|
|
