IP (clase de complejidad)
- IP (clase de complejidad)
-
Este artículo trata sobre el concepto en complejidad computacional. Para otros usos de este término, véase IP.
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.
Wikimedia foundation.
2010.
Mira otros diccionarios:
Clase de complejidad — En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada. Una clase de complejidad tiene una definición de la forma: el conjunto de los problemas de decisión que pueden … Wikipedia Español
Clase de complejidad — En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada. Una clase de complejidad tiene una definición de la forma: el conjunto de los problemas de decisión que pueden … Enciclopedia Universal
P (clase de complejidad) — Se ha sugerido que este artículo o sección sea fusionado con Tiempo polinómico (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí … Wikipedia Español
NC (clase de complejidad) — En teoría de la complejidad computacional, la clase de complejidad NC (la clase de Nick) es el conjunto de los problemas de decisión que pueden ser resueltos mediante computación paralela con un número polinómico de procesadores en tiempo… … Wikipedia Español
RE (clase de complejidad) — En complejidad computacional, RE (abreviación de recursivamente enumerable) es la clase de complejidad conformada por aquellos problemas de decisión para los cuales una respuesta sí puede ser verificada por una máquina de Turing en una cantidad… … Wikipedia Español
L (clase de complejidad) — En teoría de la complejidad computacional, la clase de complejidad L (LSPACE o espacio logarítmico determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n… … Wikipedia Español
PH (clase de complejidad) — Para otros usos del término PH, véase la página de desambiguación. En teoría de la complejidad computacional, la clase de complejidad PH es la unión de todas las clases de complejidad de la jerarquía polinómica. (Tiempo y espacio) PH está… … Wikipedia Español
ALL (clase de complejidad) — En complejidad computacional, ALL es la clase de complejidad conformada por todos los problemas de decisión. Relaciones con otras clases ALL contiene todas las clases de complejidad de problemas de decisión, incluyendo las clases RE y co RE.… … Wikipedia Español
PH (clase de complejidad) — Para otros usos del término PH, véase la página de desambiguación. En teoría de la complejidad computacional, la clase de complejidad PH es la unión de todas las clase de complejidad de la jerarquía polinómica. PH está contenida en las clases… … Enciclopedia Universal
NL (clase de complejidad) — En teoría de la complejidad computacional, la clase de complejidad NL (espacio logarítmico no determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el … Wikipedia Español
UP (clase de complejidad) — En teoría de la complejidad computacional, la clase de complejidad UP (tiempo polinómico, no determinista, no ambiguo) es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no… … Wikipedia Español
