¿Cuál es un problema natural en la teoría de la computación?

En el artículo de Stephen Cook sobre el problema P vs NP, [1] afirma lo siguiente [2]:

Tesis de viabilidad: un problema natural tiene un algoritmo factible si tiene un algoritmo de tiempo polinómico.

Mi pregunta es, ¿qué quiere decir exactamente él (o, en general, qué quiere decir uno) con "un problema natural "? Hablar de que los problemas son naturales parece ser bastante común, pero todavía tengo que encontrar una definición. Parece que me falta algo. Aquí hay un par de posibles respuestas en las que estoy pensando:

Primera respuesta posible

Cook dice en su artículo que "natural" debe explicarse. Él dice, "generalmente no consideramos que una clase con un parámetro sea natural, como el conjunto de gráficos incrustados en una superficie del género k , k > 1". [3] Ahora, en primer lugar, esto parece decir qué " natural "no es más que lo que es; pero si cada problema es natural o no y esto describe completamente todos los problemas que no son naturales, entonces esto sería suficiente para definir lo natural. (Pero el calificador "en general" sugiere que esta no es una descripción suficiente y necesaria de los problemas que no son naturales).

Creo que "clases con parámetros" se refiere a la trazabilidad de parámetros fijos, con lo cual nos referimos a problemas que tienen posibles entradas restringidas de tal manera que la viabilidad es forzada. Por lo tanto, podemos resolver el problema de la mochila [4] con un algoritmo de tiempo polinómico si fijamos el peso que puede llevar la mochila (pero en general no hay solución en tiempo polinómico). Con esto en mano, supongo que ser "natural" significa que el problema no está restringido (¿"restringido artificialmente") de una manera que obliga a un algoritmo de tiempo polinómico a salir de un problema que no se puede resolver en el tiempo polinómico?

La razón por la que no estoy seguro de que esta sea la forma correcta de entender la noción de Cook de "natural" es que no estoy absolutamente seguro de lo que está haciendo la calificación "natural" aquí. Si cae "natural", entonces obtiene "un problema tiene un algoritmo factible si tiene un algoritmo de tiempo polinomial". Pero esto parece perfectamente razonable: el problema de la mochila no tiene un algoritmo factible porque no tiene un algoritmo de tiempo polinómico; la mochila-con-fijo-paramater-tractability tiene un algoritmo factible porque tiene un algoritmo de tiempo polinómico. Ambas cuentas parecen estar de acuerdo con la noción de lo que es un problema con un algoritmo factible.

Supongo que esta podría ser la mejor guía para entender lo que significa Cook, porque Cook realmente se da vuelta y lo define. También considero que esta noción de natural es capturada por esta pregunta de StackExchange. [5}

Pero hay otro.

Segunda respuesta posible

William Gasarch en su artículo "Clasificación de problemas en clases de complejidad" [6], dice que llevará a cabo "una discusión literal sobre lo que es un problema natural" [7]. Al final del documento, [8] hay un intercambio en forma de diálogo, donde un orador dice:

"¿Qué hace que un problema sea natural? Por un lado, no construí el problema con el único propósito de no estar en P. Así que no es un problema tonto. ¿Entonces se eleva al nivel de ser natural?"

Entonces, me parece que lo que dice Gasarch es que si tenemos un problema que no se construye intencionalmente para que podamos decir que no está en P, entonces es natural. Entonces, con un poco de interpretación creativa, parece que Gasarch está diciendo algo al menos consistente con Cook: por un lado, Gasarch dice que no ser construido con el único objetivo de no estar en P hace que un problema no sea natural; y por otro lado, Cook dice que un problema es natural si no tiene parámetros. Pero la mera consistencia no produce una definición.

Tercera respuesta posible

En la entrada de Wikipedia para un "problema bien planteado" [9], se presenta una definición de la noción de Jacques Hadamard de un problema bien planteado, luego se afirma que un problema bien planteado "podría considerarse como problemas" naturales " en eso hay procesos físicos modelados por estos problemas ". Entonces, ¿un problema es natural si y solo si modela un proceso físico?

Las calificaciones de Hadamard, según Wikipedia, son (i) existe una solución, (ii) la solución es única y (iii) el comportamiento de la solución cambia continuamente con las condiciones iniciales. Esto parece ser diferente de las otras dos definiciones. Mi sensación es que "natural" no se usa exactamente de la misma manera (especialmente si estamos de acuerdo con la interpretación de que un problema es natural si y solo modela un proceso físico), pero quería incluirlo porque me encontré con en mi investigación sobre esta cuestión, y hay puntos de contacto.

Entonces mi pregunta es: ¿qué es un problema natural? ¿Alguna de estas respuestas, o alguna combinación de ellas, es correcta? ¿Hay alguna otra respuesta que me estoy perdiendo? Gracias.

1. "La declaración del problema", 2006, publicado en línea en Clay Mathematics; título: "El problema P vs NP", http://www.claymath.org/sites/default/files/pvsnp.pdf
2. pag. 3
3. pag. 4 4
4. https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem
5. ¿El problema natural más difícil conocido en P? Supongo que un problema natural sigue a esta descripción pero no restringe k a ser el más grande.
6. https://www.cs.umd.edu/~gasarch/papers/classcomp.pdf
7. pag. 2)
8. pag. 47-8, sección 25
9. https://en.wikipedia.org/wiki/Well-posed_problem

Para ser claros, no está destinado a ser formalizable. No es un teorema, es una observación sobre el mundo, está bien si "natural" es subjetivo aquí. Por analogía, si alguien dice "la diferenciación es mecánica mientras que la integración es arte", no lo están invitando a formalizar "mecánica" y "arte" y probar la afirmación, están tratando de transmitir una perspectiva general. Así que quizás te estés perdiendo un poco del bosque por los árboles aquí. [Nota al pie]

¿Cuál es el punto del autor?

Sigamos su sugerencia y dejemos caer la palabra "natural":

Tesis de viabilidad (primer borrador): un problema tiene un algoritmo factible si tiene un algoritmo de tiempo polinómico.

Bueno, esto es técnicamente incorrecto. Debido al teorema de la jerarquía de tiempo , podemos construir problemas arbitrariamente difíciles en P (por ejemplo, que requieren tiempo). Pero estos problemas de contraejemplo son muy extraños, autorreferenciales, por ejemplo, "¿se detiene la máquina de Turing dada en la entrada dada en pasos?"$n^{1000}$$n^{1000}$

Por lo tanto, el autor siente que la tesis sigue siendo bastante precisa con respecto a los problemas que realmente queremos resolver en el mundo real y otros problemas encontrados "naturalmente" en el curso de la vida de la teoría de la no complejidad. Entonces él piensa, llamemos a esos problemas "naturales" y revisemos la tesis de factibilidad.

Qué es y qué no es natural

Sin duda, un problema que surge comúnmente en la práctica se consideraría natural: caminos más cortos, clasificación, distancia de edición, búsqueda de raíces, vendedor ambulante, mochila.

Por supuesto, un problema que está pensado y definido específicamente para probar un resultado complejo, y hace referencia a la clase específica, no es natural. Por ejemplo, "puede esta cadena ser generada por una máquina de Turing en k estados en n tiempo".

Algunas cosas son menos claras, como la programación lineal, pero no me preocuparía demasiado por eso. Estudie muchos algoritmos y problemas de complejidad y vea si está de acuerdo con la idea general, o si encuentra ejemplos que cree que la contradicen.

(En cualquier caso, creo que la ruta del "problema bien planteado" definitivamente es incorrecta, como sospechas).

[nota al pie] No quiero desanimarte de tratar de formalizarlo, solo de pensar que estás destinado a hacerlo.

Se reduce aproximadamente a si la definición del problema podría ser circular:

• Un problema artificial es uno construido para llenar sus criterios de clase.

• Un problema natural no depende de su método de construcción para llenar los criterios de clase.

Se sabe que la construcción de Ladner es intermedia NP , siempre que exista NPI.

Probar cualquier candidato para problemas naturales de NPI probaría .$P \subsetneq NP$

Precaución: Buena suerte al intentar demostrar que tal candidato; Esto puede parecer un enfoque accesible, pero naturalmente ha desarrollado algunas barreras en la prueba .