Complejidad y demostraciones interactivas

Si una entrada binaria tiene longitud n, un algoritmo polinómico usa a lo sumo Cnᵏ pasos para constantes C,k independientes de la instancia. Enumerar hasta el valor del entero puede ser exponencial en su longitud.

La codificación de grafos también cuenta: una matriz de adyacencia tiene orden N² entradas para N vértices; una lista de aristas usa otra longitud. El coste de operar con enteros debe considerar sus bits si el modelo no los trata como palabras de tamaño fijo.

Una pregunta de decisión tiene respuesta sí o no: «¿existe una clique de tamaño k?». Búsqueda pide producirla. Verificación recibe una candidata y comprueba que cumple las condiciones. Una clique es un grupo de vértices distintos todos conectados entre sí.

P contiene decisiones resueltas por algoritmos deterministas polinómicos. NP permite certificar respuestas afirmativas con certificados de longitud polinómica y un verificador determinista polinómico.

NP no significa «no polinómico».

Para k vértices se comprueba que cada etiqueta pertenezca al grafo, que no haya repeticiones y que cada par tenga arista. Hay k(k−1)/2 pares. Con matriz de adyacencia, cada consulta es directa; con otras representaciones se incluye su coste.

La lista usa orden k log N bits, con una convención estándar para etiquetas de N vértices. Primero se descartan k>N y formatos inválidos; no se concede una clique mayor repitiendo etiquetas.

Un probador envía mensajes a un verificador aleatorio de tiempo polinómico. En el marco clásico IP el probador puede tener cómputo ilimitado; el verificador, rondas y comunicación están acotados polinómicamente. El verificador puede usar bits privados.

Completitud: en entradas verdaderas existe un probador honesto que consigue alta aceptación. Solidez: en entradas falsas, cualquier probador, incluso adaptativo, tiene aceptación acotada. No basta que el diálogo funcione con un colaborador que siempre diga la verdad.

Dos grafos son isomorfos si se convierten uno en otro renombrando vértices y conservando aristas. Para probar que G₀ y G₁ no son isomorfos, el verificador elige un bit b uniforme y una permutación π uniforme, y envía solo H=π(). Guarda b y π en privado.

El probador contesta un bit b′.

Si los grafos no son isomorfos, sus conjuntos de copias etiquetadas son disjuntos y un probador sin límite puede identificar de cuál procede H: completitud perfecta.

Para grafos isomorfos existe un renombrado fijo entre G₀ y G₁. Componer una permutación uniforme con ese renombrado conserva uniformidad. Por eso H tiene exactamente la misma distribución para b=0 y b=1.

Con el bit uniforme, observar H deja ambas posibilidades equiprobables. Ningún probador puede adivinarlo con probabilidad superior a 1/2. El razonamiento no presupone una heurística del adversario ni que le resulte costoso calcular: es una igualdad de distribuciones.

Repetimos k veces con bits y permutaciones nuevos independientes y aceptamos solo si todas las rondas pasan. En una entrada falsa, incluso dado el historial y las respuestas anteriores, el siguiente bit sigue oculto por el mismo argumento.

Si cada aceptación falsa condicional es como máximo 1/2, la probabilidad de pasar todas es como máximo 2⁻ᵏ, por multiplicación de probabilidades condicionales. La respuesta del probador sí puede adaptarse al pasado; lo necesario es mantener la cota condicional.

El teorema clásico IP=PSPACE identifica estas pruebas interactivas de recursos polinómicos con decisiones realizables en espacio polinómico. Su demostración usa construcciones mucho más generales que el reto de grafos. No se deduce del pequeño ejemplo.

Solidez probabilística, argumentos basados en límites de cómputo y conocimiento cero son propiedades distintas. Tampoco una cota de aceptar una falsedad se convierte automáticamente en la probabilidad posterior de que una afirmación aceptada sea verdadera.