Entscheidungsproblem - Decision problem

Ein Entscheidungsproblem hat nur zwei mögliche Ausgänge ( Ja oder Nein ) an einem Eingang.

In der Berechenbarkeitstheorie und der rechnerischen Komplexitätstheorie ist ein Entscheidungsproblem ein Problem, das als Ja-Nein-Frage der Eingabewerte gestellt werden kann. Ein Beispiel für ein Entscheidungsproblem ist die Entscheidung, ob eine bestimmte natürliche Zahl eine Primzahl ist . Ein anderes ist das Problem "Wenn zwei Zahlen x und y gegeben sind , teilt x y gleichmäßig ?". Die Antwort lautet je nach den Werten von x und y entweder "Ja" oder "Nein" . Ein Verfahren zur Lösung eines Entscheidungsproblems, das in Form eines Algorithmus angegeben wird , wird als Entscheidungsverfahren für dieses Problem bezeichnet. Ein Entscheidungsverfahren für das Entscheidungsproblem " teilt x y bei zwei Zahlen x und y gleichmäßig auf ?" würde die Schritte zur Bestimmung geben, ob x y gleichmäßig teilt . Ein solcher Algorithmus ist die lange Teilung . Wenn der Rest Null ist, lautet die Antwort "Ja", andernfalls "Nein". Ein Entscheidungsproblem, das durch einen Algorithmus gelöst werden kann, wird als entscheidbar bezeichnet .

Entscheidungsprobleme treten typischerweise in mathematischen Fragen der Entscheidbarkeit auf , dh in der Frage nach der Existenz einer wirksamen Methode zur Bestimmung der Existenz eines Objekts oder seiner Zugehörigkeit zu einer Menge; Einige der wichtigsten Probleme in der Mathematik sind unentscheidbar .

Das Gebiet der rechnerischen Komplexität kategorisiert entscheidbare Entscheidungsprobleme danach, wie schwierig sie zu lösen sind. "Schwierig" wird in diesem Sinne in Bezug auf die Rechenressourcen beschrieben , die der effizienteste Algorithmus für ein bestimmtes Problem benötigt. Das Gebiet der Rekursionstheorie kategorisiert unentscheidbare Entscheidungsprobleme nach dem Turing-Grad , der ein Maß für die Nichtberechnbarkeit ist, die jeder Lösung innewohnt.

Definition

Ein Entscheidungsproblem ist eine Ja-oder-Nein-Frage zu einer unendlichen Menge von Eingaben. Es ist traditionell, das Entscheidungsproblem als die Menge möglicher Eingaben zusammen mit der Menge von Eingaben zu definieren, für die die Antwort Ja lautet .

Diese Eingaben können natürliche Zahlen sein, können aber auch Werte anderer Art sein, z. B. binäre Zeichenfolgen oder Zeichenfolgen über einem anderen Alphabet . Die Teilmenge der Zeichenfolgen, für die das Problem "Ja" zurückgibt, ist eine formale Sprache , und häufig werden Entscheidungsprobleme als formale Sprachen definiert.

Mit einer Codierung wie der Gödel-Nummerierung kann jede Zeichenfolge als natürliche Zahl codiert werden, über die ein Entscheidungsproblem als Teilmenge der natürlichen Zahlen definiert werden kann. Daher besteht der Algorithmus eines Entscheidungsproblems darin, die charakteristische Funktion einer Teilmenge der natürlichen Zahlen zu berechnen .

Beispiele

Ein klassisches Beispiel für ein entscheidbares Entscheidungsproblem ist die Menge der Primzahlen. Es ist möglich, effektiv zu entscheiden, ob eine gegebene natürliche Zahl eine Primzahl ist, indem jeder mögliche nichttriviale Faktor getestet wird. Obwohl viel effizientere Methoden zur Prüfung der Primalität bekannt sind, reicht die Existenz einer wirksamen Methode aus, um die Entscheidbarkeit festzustellen.

Entscheidbarkeit

Ein Entscheidungsproblem ist entscheidbar oder effektiv lösbar, wenn die Menge der Eingaben (oder natürlichen Zahlen), für die die Antwort Ja lautet, eine rekursive Menge ist . Ein Problem ist teilweise entscheidbar , halbentscheidbar , lösbar oder beweisbar, wenn die Menge der Eingaben (oder natürlichen Zahlen), für die die Antwort Ja ist, eine rekursiv aufzählbare Menge ist . Probleme, die nicht entscheidbar sind, sind unentscheidbar . Für diese ist es nicht möglich, einen effizienten oder sonstigen Algorithmus zu erstellen, der sie löst. ${\ displaystyle A}$

Das Halteproblem ist ein wichtiges unentscheidbares Entscheidungsproblem; Weitere Beispiele finden Sie in der Liste der unentscheidbaren Probleme .

Komplette Probleme

Entscheidungsprobleme können nach einer Reduzierbarkeit von mehreren geordnet werden und sich auf mögliche Reduzierungen wie z. B. Polynomzeitverkürzungen beziehen . Ein Entscheidungsproblem P wird für eine Reihe von Entscheidungsproblemen S als vollständig bezeichnet, wenn P ein Mitglied von S ist und jedes Problem in S auf P reduziert werden kann . Vollständige Entscheidungsprobleme werden in der rechnergestützten Komplexitätstheorie verwendet , um Komplexitätsklassen von Entscheidungsproblemen zu charakterisieren . Zum Beispiel ist das Boolesche Erfüllbarkeitsproblem für die Klasse NP von Entscheidungsproblemen unter Polynomzeitreduzierbarkeit vollständig .

Funktionsprobleme

Entscheidungsprobleme hängen eng mit Funktionsproblemen zusammen , deren Antworten komplexer sein können als ein einfaches Ja oder Nein. Ein entsprechendes Funktionsproblem ist "bei zwei Zahlen x und y , was ist x geteilt durch y ?".

Ein Funktionsproblem besteht aus einer Teilfunktion f ; Das informelle "Problem" besteht darin, die Werte von f an den Eingängen zu berechnen, für die es definiert ist.

Jedes Funktionsproblem kann in ein Entscheidungsproblem verwandelt werden. Das Entscheidungsproblem ist nur der Graph der zugehörigen Funktion. (Der Graph einer Funktion f ist die Menge von Paaren ( x , y ), so dass f ( x ) = y .) Wenn dieses Entscheidungsproblem effektiv lösbar wäre, wäre auch das Funktionsproblem. Diese Reduzierung berücksichtigt jedoch nicht die Rechenkomplexität. Zum Beispiel ist es möglich, dass der Graph einer Funktion in der Polynomzeit entscheidbar ist (in diesem Fall wird die Laufzeit als Funktion des Paares ( x , y ) berechnet ), wenn die Funktion nicht in der Polynomzeit berechenbar ist (in der Die Falllaufzeit wird nur als Funktion von x berechnet . Die Funktion f ( x ) = 2 ^x hat diese Eigenschaft.

Jedes Entscheidungsproblem kann in das Funktionsproblem der Berechnung der charakteristischen Funktion der Menge umgewandelt werden, die dem Entscheidungsproblem zugeordnet ist. Wenn diese Funktion berechenbar ist, ist das damit verbundene Entscheidungsproblem entscheidbar. Diese Reduktion ist jedoch liberaler als die Standardreduktion, die bei der Komplexität der Berechnungen verwendet wird (manchmal als Polynom-Zeit-Viel-Eins-Reduktion bezeichnet). Beispielsweise ist die Komplexität der charakteristischen Funktionen eines NP-vollständigen Problems und seines Co-NP-vollständigen Komplements genau gleich, obwohl die zugrunde liegenden Entscheidungsprobleme in einigen typischen Berechnungsmodellen möglicherweise nicht als äquivalent angesehen werden.

Optimierungsprobleme

Im Gegensatz zu Entscheidungsproblemen, für die es nur eine richtige Antwort für jede Eingabe gibt, geht es bei Optimierungsproblemen darum, die beste Antwort auf eine bestimmte Eingabe zu finden. Optimierungsprobleme treten natürlich in vielen Anwendungen auf, wie zum Beispiel dem Problem des Handlungsreisenden und vielen Fragen in der linearen Programmierung .

Es gibt Standardtechniken, um Funktions- und Optimierungsprobleme in Entscheidungsprobleme umzuwandeln. Beispielsweise besteht beim Problem des Handlungsreisenden das Optimierungsproblem darin, eine Tour mit minimalem Gewicht zu erstellen. Das damit verbundene Entscheidungsproblem ist: für jedes N zu entscheiden, ob der Graph eine Tour mit einem Gewicht von weniger als N hat . Durch wiederholte Beantwortung des Entscheidungsproblems ist es möglich, das minimale Gewicht einer Tour zu ermitteln.

Da die Theorie der Entscheidungsprobleme sehr gut entwickelt ist, hat sich die Forschung in der Komplexitätstheorie typischerweise auf Entscheidungsprobleme konzentriert. Optimierungsprobleme selbst sind nach wie vor sowohl in der Berechenbarkeitstheorie als auch in Bereichen wie der Operationsforschung von Interesse .

Siehe auch

• ALL (Komplexität)
• Rechenproblem
• Entscheidbarkeit (Logik) - für das Problem der Entscheidung, ob eine Formel eine Folge einer logischen Theorie ist .
• Suchproblem
• Zählproblem (Komplexität)
• Wortproblem (Mathematik)

Verweise

• Kozen, DC (2012), Automata and Computability , Springer.
• Hartley Rogers, Jr. , Theorie rekursiver Funktionen und effektiver Berechenbarkeit , MIT Press, ISBN   0-262-68052-1 (Taschenbuch), ISBN   0-07-053522-1
• Sipser, M. (1996), Einführung in die Theorie der Berechnung , PWS Publishing Co.
• Robert I. Soare (1987), Rekursiv aufzählbare Mengen und Grade , Springer-Verlag, ISBN   0-387-15299-7
• Daniel Kroening & Ofer Strichman, Entscheidungsverfahren , Springer, ISBN   978-3-540-74104-6
• Aaron Bradley & Zohar Manna , Der Rechenkalkül , Springer, ISBN   978-3-540-74112-1