Principalmente, demuestra el sorprendente poder de la aleatoriedad en los sistemas de prueba. Shamir muestra que IP, el conjunto de problemas solubles por un verificador aleatorio de tiempo polinómico que se comunica de forma adaptativa con un probador todopoderoso (pero potencialmente deshonesto), es igual a PSPACE, el conjunto de problemas computables por una máquina de Turing que utiliza un espacio polinómico. El análogo libre de aleatoriedad de IP es NP, que está contenido dentro y se cree que es mucho más pequeño que PSPACE. Por supuesto, puede resultar que NP = PSPACE, en cuyo caso IP = NP y la interactividad no te dan nada, pero parece poco probable que esto sea cierto, ya que la jerarquía polinómica colapsaría.
Un ejemplo de un problema que está en IP pero que no se sabe que está en NP es el no isomorfismo gráfico. Tiene dos gráficos [matemática] G, H [/ matemática] y desea saber si no son isomórficos. No hay un certificado sucinto (de longitud polinómica) conocido para esto, pero puede hacerlo con un probador interactivo eligiendo [matemática] [/ matemática] o [matemática] H [/ matemática] uniformemente al azar, permutando los vértices y enviándolo al probador. Si [matemática] G, H [/ matemática] no son isomórficas, entonces el probador puede decirle cuál envió; si lo son, entonces ningún probador, por poderoso que sea, puede hacerlo mejor que el azar.
Curiosamente, si agrega un segundo probador (que no puede comunicarse con el primero), de repente puede calcular todo en NEXP, que se cree que es incluso más grande que PSPACE. Muchos de estos resultados de pruebas interactivas son contraintuitivos y tienen profundas implicaciones para la teoría de la complejidad.
- ¿Cuáles son algunas limitaciones de la teoría de detección de señales?
- Cómo formular matemáticamente para seleccionar los mejores valores de N de una matriz
- ¿Cómo podemos probar si un dispositivo informático en particular exhibe una aceleración cuántica?
- ¿Cuál es el algoritmo más eficiente para encontrar todos los picos 2D en una matriz?
- ¿Por qué es importante considerar las anotaciones asintóticas (como límite superior, límite inferior y límite estrecho)?
