Si P = NP para que las clases colapsen en una sola, ¿debería cambiarse el nombre de la clase solo por ‘P’?

Por lo general, estas cosas suceden con el tiempo . Por ejemplo, hubo un momento en que la gente no hablaba de eficiencia en términos de asíntóticos como la notación Big-Oh. Incluso entonces, NP no es solo una clase que es interesante con respecto a P, así que tengo mis dudas. Hay muchas desviaciones de la clase NP, por lo que creo que el concepto de eliminar NP por completo no desaparecerá pronto, incluso si P = NP. Muchos conceptos teóricos importantes de la informática generalmente ocurren entre modelos de computación deterministas y no deterministas. Incluso entonces, no todos los problemas NP-hard están contenidos dentro de la clase de problemas NP-complete (aquellos que se encuentran dentro de NP), por lo que tengo la sensación de que incluso si P = NP, el lenguaje probablemente seguirá siendo el mismo. No soy un vidente del futuro, así que no puedo decirte sí o no. Todo el campo se siente bastante cómodo con el lenguaje de la teoría de la complejidad computacional en este momento, por lo que tengo mis dudas, incluso si colapsan, la gente decidirá usar otra noción del lenguaje al describirlas.

En resumen, dudo ya que no veo el no determinismo como un concepto teórico en informática que desaparecerá pronto (incluso se demostró que P = NP en este momento), especialmente después de un problema tan infame como este arraigado en el campo. Debo enfatizar que hay áreas enteras de la Ciencia de la Computación Teórica en torno a las clases relacionadas con estas clases de complejidad computacional, y están haciendo algunas de las investigaciones de Algoritmos teóricos más importantes en estos días en un intento de lidiar con diversas situaciones para P vs. NP y otras conjeturas importantes en nuestro campo (p. Ej., Complejidad parametrizada, Algoritmos de aproximación, entre otros).

Pero si quieres mi opinión sobre si debería renombrarse, no , no lo creo. Como concepto teórico, NP es muy valioso tanto pedagógicamente como teóricamente.

De hecho, podemos mirar al pasado en busca de ejemplos similares.

Un resultado no trivial en la teoría de la complejidad es que IP = PSPACE.

IP es la clase de problemas que se pueden resolver mediante un “sistema de prueba interactivo. PSPACE es la clase de problemas que se pueden resolver en una cantidad de espacio polinomial.

El hecho de que IP = PSPACE es un resultado bastante no trivial, y es sorprendente.

Entonces, podemos preguntar: después de probar IP = PSPACE, ¿dejamos de llamarlo IP y simplemente lo llamamos PSPACE?

Bueno no. Por un lado, las pruebas de IP = PSPACE son confusas. OK, pero fuera de eso? Bueno, todavía es bueno tener dos nombres. Dado que si vamos a hablar sobre otras clases de complejidad que usan variantes en pruebas interactivas, como QIP (pruebas interactivas cuánticas) o MIP (pruebas interactivas multiprover), tiene sentido simplemente llamar a IP “IP”.

Entonces, de la misma manera, probablemente no dejaríamos de usar el nombre NP incluso si probáramos P = NP. Generalmente esto es cierto cuando mostramos que dos objetos matemáticos son iguales, si la prueba no es trivial.

En realidad, hay otra razón para no renunciar al nombre NP, en el caso de la teoría de la complejidad. Incluso si P = NP, no es posible usar indistintamente los nombres P y NP en todas partes. Hay algo en la teoría de la complejidad llamado notación de oráculo , que puede ser confuso exactamente por esta razón. La notación de Oracle se escribe como exponenciación; [matemática] \ textf {NP} ^ A [/ matemática] significa “la clase de complejidad solucionable por una máquina no determinista con un oráculo a A” (donde A es algún problema, como “SAT” o “El problema de detención” o incluso solo una función aleatoria).

Ahora, lo complicado es que incluso si P = NP, eso no significa [matemática] \ textf {P} ^ A = \ textf {NP} ^ A [/ matemática]. (De hecho, se sabe que existe una A tal que [matemática] \ textf {P} ^ A = \ textf {NP} ^ A [/ matemática].)

La cuestión es que P y NP y otras clases no solo se refieren al conjunto de problemas que pueden resolverse mediante ciertos modelos computacionales. En general, P y NP pueden referirse a esos modelos computacionales. Pero escribimos P = NP, solo queremos decir que esos conjuntos de problemas son iguales.

Entonces, incluso si P = NP, todavía es el caso de que los símbolos P y NP tienen sus propios significados distintos.

Si P = NP, entonces la clase ya se llamaría P. Entonces cambiarle el nombre a P no tendría ningún sentido. De lo que estás hablando es de eliminar el nombre NP, que también se llamaría. No veo ninguna razón o posibilidad de hacerlo. Causaría mucha confusión al leer y hablar sobre trabajos antiguos. ¿Cómo explicarías el sorprendente resultado reciente que P = P a los estudiantes?

También te encontrarás con problemas que la pregunta P vs NP no relativiza. Esto significa que hay oráculos [matemática] A [/ matemática] y [matemática] B [/ matemática] tales que [matemática] \ matemática {P} ^ A = \ matemática {NP} ^ A [/ matemática] pero [matemática] ] \ mathrm {P} ^ B \ neq \ mathrm {NP} ^ B [/ math]. El uso de P en lugar de NP podría dar lugar a respuestas incorrectas o impedir la investigación.

Probablemente. P puede definirse como “Tiempo polinómico”. NP puede definirse como tiempo polinomial no determinista ”.

Si P = NP, eso significaría que hemos encontrado una manera de resolver los problemas de NP en el tiempo polinómico. Se deduce lógicamente que este espacio de problemas se llamaría “P” (o al menos se llamaría algo completamente distinto).