¿Dónde surge exactamente NP? Una relectura estructural de la formulación original de Cook

Este artículo reexamina la formulación original de Cook del problema P versus NP. La cuestión central no es si \(P=NP\) o \(P\neq NP\), sino dónde, en la construcción original, NP surge como una clase computacional genuinamente nueva.

La formulación de Cook procede desde el cómputo determinista en tiempo polinómico hasta una relación \(R(x,y)\) decidible en tiempo polinómico, y luego hasta la forma extendida existencialmente \[L=\{x\mid \exists y\,R(x,y)\}.\] Sostenemos que esta transición introduce un parámetro finito adicional y un cuantificador existencial, pero no introduce explícitamente un nuevo mecanismo computacional.

El artículo observa además que expresiones de potencia finita como \(n^x\) y \(x^n\), cuando ambos parámetros son finitos y están dados, siguen siendo objetos polinómicos. Así, la aparición de una clase supuestamente nueva requiere una justificación adicional más allá de la mera introducción de un parámetro de certificado.

Por lo tanto, el propósito de este artículo no es resolver el problema P versus NP, sino cuestionar si NP aparece como una clase distinta dentro de la definición original de Cook en absoluto.

Palabras clave: P versus NP; NP \(_{Cook}\); formulación de Cook; relaciones polinómicas; estructuras finitas; verificación existencial; certificados; simetría de parámetros; dependencia de la representación; complejidad interpretativa; fundamentos de la computación