¿Por qué los problemas de decisión se usan comúnmente en la teoría de la complejidad?

De Wikipedia :

El tipo de problema computacional: los problemas más utilizados son los problemas de decisión . Sin embargo, las clases de complejidad se pueden definir en función de problemas de función, problemas de conteo, problemas de optimización, problemas de promesa, etc.

También vi que las definiciones de NP-complete, NP-hard, NP, ..., se definen solo para problemas de decisión. Me pregunto por qué ese es el caso?

¿Es porque cualquier otro problema puede convertirse de manera equivalente en un problema de decisión?

A menudo, los problemas de decisión se usan porque permiten una definición precisa y simple del problema y, como se indicó, muchos otros problemas pueden convertirse en un problema de decisión equivalente.

Otros tipos de problemas también se consideran en la teoría de la complejidad, por ejemplo, problemas de función y problemas de búsqueda .

Probablemente hay muchas maneras diferentes de responder a esta pregunta, sin embargo, un elemento clave es un precedente histórico. La prueba de la existencia de un algoritmo para el problema de detención en 1936 por Turing utiliza el problema de detención como un problema de decisión. esto a su vez se basó (y resolvió negativamente) en el problema de Hilberts Entscheidungs (1928) que solicitó un método sistemático para determinar la verdad o la falsedad de cualquier enunciado matemático bien formado, es decir, también un problema de decisión.

Esto, a su vez, tiene cierta similitud con el décimo problema de Hilbert, que data de 1900, que pide la solución de ecuaciones enteras de diofantina (muchos de sus 23 problemas de investigación fronterizos / fundamentales se plantearon como problemas de decisión). Sin embargo, tenga en cuenta que el problema de Entscheidungs ​​incluso se basó en un concepto mucho más antiguo de Leibniz como afirma Wikipedia:

El origen del problema de Entscheidungs ​​se remonta a Gottfried Leibniz, quien en el siglo XVII, después de haber construido una máquina calculadora mecánica exitosa, soñaba con construir una máquina que pudiera manipular símbolos para determinar los valores de verdad de las declaraciones matemáticas.

También tenga en cuenta que las ecuaciones de Diophantine datan de los griegos que fueron algunos de los primeros en considerar, estudiar y enfatizar la importancia de la prueba matemática. Hay al menos dos problemas importantes de la teoría de números, aún sin resolver con mucha investigación moderna, debido a los griegos: la existencia de números primos gemelos infinitos y la existencia de números perfectos impares .

tenga en cuenta algunos "problemas de decisión" (es decir, en la forma de buscar pruebas para abrir conjeturas matemáticas) literalmente tomó cientos de años para resolver, por ejemplo, el último teorema de Fermats , más de 3,5 siglos, también en teoría de números.

por lo tanto, los problemas de decisión son muy antiguos, pero aun cuando se establezcan de manera simple, pueden ser extremadamente difíciles y están esencialmente enraizados en la pregunta "¿es esta afirmación verdadera o falsa" en relación con la existencia de la (s) prueba (s)? en el fondo es un concepto matemático central. Además, sigue apareciendo en lugares modernos de una manera fundamental y que recuerda, como la pregunta P vs NP (~ 1971), donde la clase NP se puede definir / enmarcar en términos de detención de una máquina NP y solución del problema de satisfacción en el tiempo P .