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.
Datos:Q1665886
Agosto 06, 2021
clase, complejidad, sistema, demostración, interactivo, concepto, teoría, complejidad, computacional, modela, cómputos, como, intercambio, mensajes, entre, partes, partes, verificador, demostrador, quienes, interactúan, intercambio, mensajes, para, demostrar, . Un sistema de demostracion interactivo IP es un concepto en teoria de la complejidad computacional que modela computos como el intercambio de mensajes entre dos partes Las partes son el verificador y el demostrador quienes interactuan 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 computo acotado El verificador realiza preguntas al demostrador un numero limitado de veces para determinar si la palabra dada pertenece o no al lenguaje Este concepto de computo como interaccion 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 interaccion llamado clase de complejidad IP es equivalente al conjunto de todos los lenguajes reconocibles por una maquina de Turing usando espacio polinomico Usualmente en un sistema de demostracion interactivo el verificador puede almacenar conocimiento previo Si ese conocimiento es publico es decir visible por el demostrador el sistema de demostracion es llamado Protocolo Arturo Merlin Esta nocion fue introducida por Badai y otros Mas adelante Goldwasser y Sipser demostraron que el conjunto de lenguajes que tienen pruebas interactivas con conocimiento privado tambien tienen pruebas interactivas con conocimiento publico Datos Q1665886Obtenido de https es wikipedia org w index php title IP clase de complejidad amp oldid 123650503, wikipedia, wiki, leyendo, leer, libro, biblioteca,
