Sistema de prueba interactivo

En la teoría de la complejidad computacional , un sistema de prueba interactivo es una máquina abstracta que modela la computación como el intercambio de mensajes entre dos partes: un probador y un verificador . Las partes interactúan intercambiando mensajes para determinar si una determinada cadena pertenece o no a un idioma . El probador posee recursos computacionales ilimitados pero no se puede confiar, mientras que el verificador tiene un poder de cómputo limitado pero se supone que siempre es honesto. Se envían mensajes entre el verificador y el probador hasta que el verificador tiene una respuesta al problema y se ha "convencido" de que es correcta.

La naturaleza específica del sistema y, por lo tanto, la clase de complejidad de los lenguajes que puede reconocer, depende del tipo de límites que se pongan en el verificador, así como de las habilidades que se le otorguen; por ejemplo, la mayoría de los sistemas de prueba interactivos dependen críticamente de la la capacidad del verificador para tomar decisiones aleatorias. También depende de la naturaleza de los mensajes intercambiados: cuántos y qué pueden contener. Se ha encontrado que los sistemas de prueba interactivos tienen algunas implicaciones importantes para las clases de complejidad tradicionales definidas usando una sola máquina. Las principales clases de complejidad que describen los sistemas de prueba interactivos son AM e IP .

Cada sistema de prueba interactivo define un lenguaje formal de cadenas . La solidez del sistema de prueba se refiere a la propiedad de que ningún probador puede hacer que el verificador acepte la declaración incorrecta, excepto con una pequeña probabilidad. El límite superior de esta probabilidad se denomina error de solidez de un sistema de prueba. Más formalmente, para cada probador y cada :${\ estilo de visualización L}$${\ estilo de visualización y \ no \ en L}$${\displaystyle ({\tilde {\mathcal {P}}})}$${\ estilo de visualización y \ no \ en L}$

para algunos Siempre que el error de solidez esté limitado por una fracción polinomial del tiempo de ejecución potencial del verificador (es decir , ), siempre es posible amplificar la solidez hasta que el error de solidez se convierta en una función insignificante en relación con el tiempo de ejecución del verificador. Esto se logra repitiendo la prueba y aceptando solo si se verifican todas las pruebas. Después de las repeticiones, el error de solidez se reducirá a . ^[1]${\ estilo de visualización \ épsilon \ ll 1}$${\displaystyle \epsilon \leq 1/\mathrm {poli} (|y|)}$${\displaystyle \ell }$${\displaystyle \epsilon }$${\displaystyle \epsilon ^{\ell }}$

La clase de complejidad NP puede verse como un sistema de prueba muy simple. En este sistema, el verificador es una máquina de tiempo polinomial determinista (una máquina P ). El protocolo es:

En el caso de que exista un certificado de prueba válido, el probador siempre puede hacer que el verificador acepte entregándole ese certificado. Sin embargo, en el caso de que no haya un certificado de prueba válido, la entrada no está en el idioma, y ​​ningún probador, por malicioso que sea, puede convencer al verificador de lo contrario, porque cualquier certificado de prueba será rechazado.

Representación general de un protocolo de prueba interactivo.