Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Berechenbarkeits- und Komplexitätstheorie (http://www.informatikerboard.de/board/board.php?boardid=15)
----- Entscheidbar ob Sprachen einer Komplexitätsklasse angehören? (http://www.informatikerboard.de/board/thread.php?threadid=4104)
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).
Forensoftware: Burning Board, entwickelt von WoltLab GmbH