¿Por qué el problema abierto de P vs PSPACE no es tan importante como P vs NP dado que NP está contenido en PSPACE?

Honestamente, ninguno de los problemas merece tanta atención particular del lector lego. Creo que se deriva del mismo lugar que el aluvión de preguntas más rápidas que la luz que vemos tan a menudo en Quora.

P: ¿No sería genial si P = NP?

A: supongo. Pero no lo es.

P: ¿Pero no sería genial si lo fuera?

A: supongo.

P: Leí un gran artículo que decía que un tipo lo demostró.

A: Ese artículo fue una mierda.

P: ¡Pero significa que podría ser posible!

A: No, no lo hace.

Es casi seguro que P no es NP, lo que significa que es aún menos probable que P = PSPACE. Una prueba de que P! = PSPACE sería interesante como una dirección para una prueba de que P! = NP.

Entonces, ¿por qué no recibe “atención de los medios”? ¿Quién diablos lo sabe? Es efectivamente un meme, no muy diferente de los tablones o los lolcats. La atención de los medios que se le presta no revela prácticamente nada. Es la versión informática de la cita de Cyanide & Happiness, “No te gusta la ciencia, solo estás mirando su trasero cuando pasa”. Probablemente tiene algún tipo de base en la noción de que podríamos hacer todo tipo de cosas realmente difíciles en poco tiempo si P = NP, y eso hace que la falta de una prueba de alguna manera sea sugerente. Pero toda falta de prueba significa que la prueba resulta ser difícil. Nadie le garantizó que los conceptos fáciles tuvieran pruebas fáciles, véase el último teorema de Fermat.

Cuando alguien finalmente tenga uno, tendremos muchas conversaciones que suenan como las que tuvimos con FLT:

P: Hey, probamos P! = NP. ¿Que hacemos con eso?

A: nada. Ya pensamos que era verdad y hemos estado trabajando sobre esa base.

P: ¿Qué quieres decir con nada? Fue tan difícil que tiene que ser bueno para algo.

R: Bueno, en realidad, es un avance interesante en [campo menor del que nunca has oído hablar].

P: ¿Y me van a construir autos voladores?

R: No. No hay aplicaciones tecnológicas previsibles para ese campo, pero ¿quién sabe?

P: Entonces, ¿por qué todos estaban tan entusiasmados con esto?

A: No tengo una maldita idea.

Re: “¿No parece más difícil de mostrar que P vs NP?”:

Sería más fácil mostrar P! = PSPACE que mostrar P! = NP. Sería más difícil mostrar P = PSPACE que mostrar P = NP.

Dicho esto, todas estas cosas son muy difíciles de mostrar, ya que nadie ha mostrado ninguna de ellas, ni nadie parece tener una idea realmente buena de cómo hacerlo.

Pero la atención de los medios no es enteramente una función de tal dureza; después de todo, puedo resolver problemas abiertos arbitrariamente difíciles que no recibirán la atención de los medios.

La atención es en gran medida una función de la historia; la gente comenzó a hablar de P vs. NP hace un tiempo, se “pegó”, y ahora la gente continúa hablando de eso como algo importante. Tiene un premio de un millón de dólares, etc. Esto no se debe a que mostrar P! = PSPACE no sería un logro tremendo, o porque no tiene sentido tratar de mostrar NP! = Co-NP, o qué tienes . Es solo una peculiaridad aleatoria de la historia.

Porque los problemas en NP son mucho más notorios. Si desea hacer algoritmos pragmáticos para usar, siempre intentamos que los problemas se asienten en P tanto como sea posible. NP contiene una gran cantidad de problemas extremadamente pragmáticos para resolver problemas. P vs PSPACE no es tan importante debido a los problemas que contienen y sus implicaciones. La complejidad del espacio normalmente no es tan importante como la complejidad del tiempo, pero ambos son cruciales. Tenga en cuenta que también hay cierta intuición que tienen los científicos informáticos sobre cómo funciona el tiempo frente al espacio. Entendemos que hay una compensación, por lo que ese tipo de fenómeno no es tan interesante.

Estoy totalmente en desacuerdo con la respuesta de Joshua de que carece de importancia para los laicos. Tiene casi todo que ver con la investigación de algoritmos modernos. Si quieres entender algo que hacemos, necesitas P vs. NP. También vale la pena señalar que la resolución más pragmática de P vs. NP, el uso de algoritmos de aproximación depende en gran medida de los resultados relacionados con P vs. NP que llamamos resultados de dureza de aproximación. Todo lo que construimos en esa área depende de P vs. NP de alguna forma mientras tratamos de aproximar soluciones factibles demostrablemente buenas en tiempo polinómico. Estos algoritmos de aproximación son de extrema utilidad en la práctica porque a menudo son extremadamente eficientes y fáciles de implementar.

Como investigador, puedo decirle que las guías de P vs. NP investigan al igual que la hipótesis de Riemann. Los investigadores generalmente no lo atacan de frente, pero lo usamos todo el tiempo para probar nuevos resultados (por ejemplo, si asume P! = NP, entonces podemos decir ____), pero la forma en que organizamos los problemas generalmente es más interesante en el caso de P vs. NP, especialmente en algoritmos.