Paisaje de sistemas de prueba interactivos

Mi primera pregunta es si la caracterización de un sistema de prueba interactivo es conocida para todas las clases de complejidad clásicas. Llamaría P, NP, PSPACE, EXP, NEXP, EXPSPACE, funciones recursivas y recursivamente enumerables clásicas (entre otras). Específicamente, ¿se conoce una caracterización de sistema de prueba interactiva para funciones recursivas y recursivamente enumerables?

Solo sé que IP = PSPACE y que MIP = NEXPTIME. Por 'saber' significa que entiendo las definiciones de objetos en ambos lados de la igualdad y posiblemente entiendo la igualdad.

Mi segunda pregunta es si hay un resumen gráfico de los diferentes tipos de sistemas de prueba interactivos y las clases de complejidad que caracterizan.

Específicamente, me gustaría una referencia a una figura similar a la imagen de Immerman de caracterizaciones de complejidad de descripción .

Puede encontrar muchas caracterizaciones (particularmente en verificadores acotados por el espacio) en la famosa encuesta de Condon: La complejidad de los sistemas de prueba interactivos acotados por el espacio .

Aquí hay una lista de algunos de ellos:

• , donde 2pfa (el verificador) es un autómata finito probabilístico de dos vías.$\mathsf{RE} = \mathsf{weak\mbox{-}IP(2pfa)}$

• , donde pfa (el verificador) es un autómata finito probabilístico unidireccional que interactúa con dos probadores.$\mathsf{R} = \mathsf{2IP(pfa)}$

• .$\mathsf{NEXP} = \mathsf{2IP(pfa,poly\mbox{-}time)}$

• .$\mathsf{PSPACE} = \mathsf{IP(log\mbox{-}space,poly\mbox{-}time)}$

• .$\mathsf{NP} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,poly\mbox{-}time)} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,log\mbox{-}random\mbox{-}bits)}$

• , E X P = A M ( p o l y - s p a c e ) , etc.$\mathsf{P} = \mathsf{AM(log\mbox{-}space)}$$\mathsf{EXP} = \mathsf{AM(poly\mbox{-}space)}$

Algunos resultados recientes (en su mayoría cuánticos):

• porYakaryilmaz, donde 2qcfa (el verificador) es un autómata finito bidireccional que tiene un registro cuántica constante de tamaño.$\mathsf{RE} = \mathsf{weak\mbox{-}AM(2qcfa)}$

• porYakaryilmaz, donde 2pca (el verificador anterior) es un autómata finito probabilístico de dos vías con un contador y 2qca (el último verificador) es un dos autómata cuántico finito con un contador.$\mathsf{R} = \mathsf{IP(2pca)} = \mathsf{AM(2qca)}$

• Ito, Kobayashi y Watrous dieron una nueva caracterización de basada en sistemas de prueba interactivos cuánticos con una brecha doble exponencialmente pequeña en la probabilidad de aceptación entre los casos de integridad y solidez.$\mathsf{EXP}$

• porJain, Ji, Upadhyay y Watrous, donde QIP es la generalización cuántica de los sistemas IP.$\mathsf{PSPACE} = \mathsf{QIP(poly\mbox{-}time)}$

• $\mathsf{NP}$

• $\mathsf{NL} = \mathsf{weak\mbox{-}oneway\mbox{-}IP(2pfa,constant\mbox{-}random\mbox{-}bits)}$

NP se caracteriza a menudo como un sistema de prueba en el que el probador envía una prueba de longitud polinómica a un verificador determinístico de tiempo polinomial, y después del cual no hay interacción. La clase de lenguajes recursivamente enumerables se puede caracterizar de manera similar reemplazando "polinomio" por "finito".

Además, dado que la clase de lenguajes recursivos R es la intersección de RE y coRE, puede caracterizar a R como un sistema de prueba en el que un probador todopoderoso puede convencer a un verificador de tiempo finito tanto en la validez de las afirmaciones correctas como en la invalidez de afirmaciones falsas.

La clase EXP tiene una caracterización en términos de un sistema de prueba con "demostradores competidores", es decir, un sistema de prueba en el que hay un demostrador que intenta convencer al verificador de que la afirmación es verdadera y un refutador que intenta convencer al verificador de que El reclamo es falso. Para más detalles, ver el artículo "Haciendo cortos los juegos" de Feige y Kilian.