¿Cómo sabemos que el problema P versus NP es un problema NP sí mismo?

Question

He estado haciendo algunas investigaciones sobre el problema P versus NP. En varias ocasiones, he visto a personas decir que el problema en sí es un problema NP. He tenido curiosidad por saber cómo lo sabemos. Si sabemos que el problema es NP, entonces ¿alguien ha ideado un algoritmo que podría ejecutarse en una máquina Turing no determinista para resolver el problema en tiempo polinómico? ¿O hay alguna otra razón por la que sabemos que el problema es NP?

Gracias por cualquier respuesta de antemano

Answer 1

El problema de "P versus NP" es una sola pregunta sí-no: ¿es <span class="math-container">%-%-%</span>? La respuesta correcta es "sí" o "no", simplemente no sabemos cuál. Sin embargo, la complejidad de la respuesta es <span class="math-container">%-%-%</span>.