Warum werden Entscheidungsprobleme in der Komplexitätstheorie häufig verwendet?

Aus Wikipedia :

Die Art des Rechenproblems: Die am häufigsten verwendeten Probleme sind Entscheidungsprobleme . Komplexitätsklassen können jedoch basierend auf Funktionsproblemen, Zählproblemen, Optimierungsproblemen, Versprechenproblemen usw. definiert werden.

Ich habe auch gesehen, dass die Definitionen von NP-vollständig, NP-hart, NP, ... nur für Entscheidungsprobleme definiert sind. Ich frage mich, warum das so ist.

Liegt es daran, dass jedes andere Problem gleichwertig in ein Entscheidungsproblem umgewandelt werden kann?

Oft werden Entscheidungsprobleme verwendet, weil sie eine genaue und einfache Definition des Problems ermöglichen und, wie bereits erwähnt, viele andere Probleme in ein gleichwertiges Entscheidungsproblem umgewandelt werden können.

In der Komplexitätstheorie werden auch andere Arten von Problemen berücksichtigt, beispielsweise Funktionsprobleme und Suchprobleme .

Es gibt wahrscheinlich viele verschiedene Möglichkeiten, diese Frage zu beantworten. Ein Schlüsselelement ist jedoch der historische Präzedenzfall. die Widerlegung der Existenz eines Algorithmus für das Halteproblem 1936 von Turing verwendet das Halteproblem als ein Entscheidungsproblem. Dies beruhte wiederum auf Hilberts Entscheidungsproblem (1928) (und wurde negativ gelöst ), das nach einer systematischen Methode zur Bestimmung der Wahrheit oder Falschheit einer wohlgeformten mathematischen Aussage, dh auch eines Entscheidungsproblems, fragte.

Dies hat wiederum eine gewisse Ähnlichkeit mit Hilberts 10. Problem aus dem Jahr 1900, das nach der Lösung ganzzahliger diophantinischer Gleichungen fragt (viele seiner 23 Grenz- / Schlüsselforschungsprobleme wurden als Entscheidungsprobleme angegeben). Beachten Sie jedoch, dass das Entscheidungsproblem sogar auf einem viel früheren Konzept von Leibniz beruht, wie es in Wikipedia heißt:

Der Ursprung des Entscheidungsproblems geht auf Gottfried Leibniz zurück, der im 17. Jahrhundert nach dem Bau einer erfolgreichen mechanischen Rechenmaschine davon träumte, eine Maschine zu bauen, die Symbole manipulieren konnte, um die Wahrheitswerte mathematischer Aussagen zu bestimmen.

Beachten Sie auch, dass diophantinische Gleichungen auf die Griechen zurückgehen, die zu den ersten gehörten, die die Bedeutung mathematischer Beweise betrachteten, studierten und betonten. Es gibt mindestens zwei wichtige Probleme aus der Zahlentheorie, die aufgrund der Griechen mit viel moderner Forschung noch ungelöst sind: die Existenz unendlicher Zwillingsprimzahlen und die Existenz ungerader perfekter Zahlen .

Beachten Sie, dass einige "Entscheidungsprobleme" (dh in Form der Suche nach Beweisen für offene mathematische Vermutungen) buchstäblich Hunderte von Jahren gedauert haben , um z. B. Fermats Last Theorem , über 3,5 Jahrhunderte, auch in der Zahlentheorie, zu lösen .

Entscheidungsprobleme sind also sehr alt, aber selbst wenn sie einfach ausgedrückt werden, können sie äußerst schwierig sein und wurzeln im Wesentlichen in der Frage "Ist diese Aussage wahr oder falsch?" in Bezug auf das Vorhandensein von Beweisen. Im Kern ist es ein mathematisches Kernkonzept. Darüber hinaus taucht es an modernen Orten auf grundlegende und erinnernde Weise wieder auf, wie beispielsweise in der P-gegen-NP-Frage (~ 1971), in der die NP-Klasse definiert / umrahmt werden kann, um eine NP-Maschine anzuhalten und das Erfüllbarkeitsproblem in der P-Zeit zu lösen .