Es bien sabido que el conjunto de lenguajes que tienen sistemas de prueba interactivos de dos probadores, en los que el verificador se ejecuta en tiempo polinómico (MIP), es NEXP. ¿Pero hay límites conocidos en el poder de tales pruebas interactivas cuando los probadores tienen un poder restringido? Por ejemplo, ¿cuál es la clase de lenguajes que admiten pruebas interactivas de dos probadores con probadores de tiempo polinómico?
Más precisamente, digamos que en una entrada x, permito a los probadores un tiempo de cálculo previo arbitrario, pero una vez que comienza la interacción con el verificador, se restringen al uso de espacio polinomial (incluido el almacenamiento de los resultados de cualquier cálculo previo) y el tiempo polinómico calcular sus respuestas a la pregunta del verificador. Supongamos también que estos límites de espacio y tiempo son un polinomio fijo en la longitud de las preguntas que enviará el verificador (en lugar de la longitud de x), para evitar una solución más trivial en la que el verificador de alguna manera agotaría El espacio del probador está limitado al hacer polinomialmente más preguntas.
Claramente, esto es suficiente para NP. ¿Qué hay de PSPACE? Si solo hubiera un límite de espacio, podrían hacerlo, pero ¿qué pasa con el límite de tiempo? ¿Hay resultados interesantes en esa dirección?
También estoy interesado en otras limitaciones que uno podría considerar en los probadores. Uno de ellos sería la cantidad de verificador de comunicación -> verificador, que creo que se ha estudiado a fondo en el contexto de los PCP. ¿Cuáles son las otras restricciones interesantes?
Si los dos probadores están restringidos a ser dos máquinas BQP que no se comunican entre sí, pero comparten enredos, mientras el verificador está en BPP, entonces los dos probadores pueden probar cualquier lenguaje en BQP al verificador clásico utilizando la Computación Cuántica Universal Blind protocolo de Broadbent, Fitzsimons y Kashefi. Este protocolo también ha sido utilizado por los mismos autores como un bloque de construcción para mostrar QMIP = MIP * .
fuente