Entscheidungsproblem
Einfache Sprache
Ein Entscheidungsproblem ist durch die Antwortmöglichkeiten Ja und Nein charakterisiert.
Ein Entscheidungsproblem ist ein Tripel $(L,U,\Sigma)$, wobei $L,U\in\Sigma^*$, also $L,U$ sind Sprache über dem Alphabet $\Sigma$, und $L\subseteq U.$ Ein Algorithmus $A$ löst das Entscheidungsproblem $(L,U,\Sigma)$, wenn f.a. $x\in U$ gilt:
- $x\in L\implies A(x)=1$
- $x\not\in L\implies A(x)=0$ . Polynomialzeit
Beziehung NEA und Entscheidbarkeit
Wann entscheidet ein NEA eine Sprache $L$?
- wenn es für jedes Wort $w\in L$ mind. einen Rechenweg gibt, der $w$ akzeptiert,
- wenn jeder akzeptierende Rechenweg in Polynomialzeit läuft und
- wenn für jedes Wort $W\not\in L$ jeder Rechenweg $w$ ablehnt.