El PCP teorema establece que:
Cada decisión problema en NPse ha probabilísticamente seleccionable pruebasde constante de la complejidad de la consultay logarítmica de la aleatoriedad de la complejidad.
¿Alguien puede dar una explicación intuitiva de cómo puede hacerse esto?
Enlaces
Una explicación detallada se puede encontrar en muchos lugares. Te voy a proporcionar una interfaz intuitiva.
Por Cook-Levin teorema, el Booleano satisfiability problema es NP-completo - es decir. cada decisión problema en NP se puede reducir a ella. Vamos a pedirle a nuestro armario para el suministro de la entrada y la salida de cada puerta en el circuito y considerar esto como la prueba de que x∈Lx∈L.
Si fuéramos a parar allí, y entonces el armario podría engañar por el cambio de un solo bit en su prueba, lo que nos obligaría a revisar un grande (no constante) número de bits en el mismo. Así que debemos pedir algo más en el armario. Este algo más será la codificación de su prueba el uso de algunos (especial) corrección de errores de código. Intuitivamente, este "manchas" el falso bits en un gran número de bits en el código de la palabra.
El verificador recibe una palabra de el armario, hay 2 maneras en que el armario podría tratar de hacer trampa, esta palabra no puede ser un código de word en la opción de código, o podría ser la codificación de algo que no es una prueba. Vamos a examinar el (ligeramente diferente) la separación de los casos de la palabra está lejos de cada palabra (un gran número de bits debe ser cambiado para llegar a una palabra clave) o que está cerca, a la palabra que no es una codificación de una prueba.
Para ser capaz de detectar estos exigimos que nuestro código tiene los siguientes 2 propiedades: 1) a nivel local seleccionable - podemos, mediante la lectura de un número constante de bits, detectar w.h.p si una palabra está lejos de cualquier palabra. 2) a nivel local descifrable - podemos, mediante la lectura de un número constante de bits, decodificar w.h.p un poco de la palabra codificada. (la búsqueda de este tipo de códigos es duro, hadamard tiene estas características, pero el código de la palabra del tamaño es exponencial, RM códigos tienen estas propiedades también (en menor grado) y ellos son los que generalmente se utiliza.
Por lo que el verificador comprueba si la palabra está cerca de ser un código de palabra (con el uso de 1), y si la prueba tiene éxito, elige una al azar puerta y decodifica sus salidas y de salida (uso 2). esto es suficiente para lograr constante de la complejidad de la consulta y logarítmica de la aleatoriedad.
Cabe mencionar que (Dinur) tiene una combinatoria prueba de la PCP, que es bastante diferente de lo que he lo descrito, pero su versión es (para mí, al menos) menos intuitiva.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
