Entscheidungsproblem

Einfache Sprache

Ein Entscheidungsproblem ist durch die Antwortmöglichkeiten Ja und Nein charakterisiert.

Def. Entscheidungsproblem

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$ und
• $x\not\in L\implies A(x)=0$ .

Beziehung NEA und Entscheidbarkeit

Wann entscheidet ein NEA eine Sprache $L$?

1. wenn es für jedes Wort $w\in L$ mind. einen Berechnung gibt, der $w$ akzeptiert,
2. wenn jeder akzeptierende Berechnung in Polynomialzeit läuft und
3. wenn für jedes Wort $W\not\in L$ jeder Berechnung $w$ ablehnt.

Varianten

• Probabilistische Entscheidbarkeit

Wichtige Entscheidungsprobleme

Für Komplexitätstheorie:

• Cliquenproblem
• Teilsummenproblem
• Färbungsproblem
• 3-dimensional matching
• Problem der exakten Überdeckung
• Partition
• Rucksackproblem
• Hamiltonkreisproblem
• Traveling Salesman Problem
• Scheduling

Für Berechenbarkeitstheorie:

• Allgemeines Wortproblem für Turingmaschinen