IP (clase de complejidad)
De Wikipedia, la enciclopedia libre
Un sistema de demostración interactivo (IP) es un concepto en teoría de la complejidad computacional que modela cómputos como el intercambio de mensajes entre dos partes. Las partes son el verificador y el demostrador, quienes interactúan por intercambio de mensajes para demostrar la pertenencia o no de una palabra dada a un lenguaje. El demostrador dispone de todos los recursos que necesite pero el verificador tiene un poder de cómputo acotado. El verificador realiza preguntas al demostrador un número limitado de veces para determinar si la palabra dada pertenece o no al lenguaje.
Este concepto de cómputo como interacción entre dos partes fue propuesto por Babai y otros y por Goldwasser y otros. Se ha demostrado que el conjunto de todos los lenguajes reconocibles por interacción (llamado clase de complejidad IP) es equivalente al conjunto de todos los lenguajes reconocibles por una máquina de Turing usando espacio polinómico.
Usualmente, en un sistema de demostración interactivo, el verificador puede almacenar conocimiento previo. Si ese conocimiento es público (es decir, visible por el demostrador), el sistema de demostración es llamado Protocolo Arturo-Merlín. Esta noción fue introducida por Badai y otros. Más adelante Goldwasser y Sipser demostraron que el conjunto de lenguajes que tienen pruebas interactivas con conocimiento privado también tienen pruebas interactivas con conocimiento público.
| clases de complejidad más importantes |
| L | NL | P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C |
| PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH |
