Pruebas probabilísticamente comprobables
Estoy familiarizado con muchos resultados que usan el teorema de PCP (principalmente en algoritmos de aproximación), pero nunca he encontrado una explicación clara del teorema de PCP (es decir, que ).N P = P C P (O(log( n ) ) , O ( 1 ) )nortePAGS=PAGSCPAGS(O(Iniciar sesión(norte)),O(1))\mathsf{NP}...
Suponga que y son dos gráficos no dirigidos en el conjunto de vértices . Los gráficos son isomórficos si y solo si hay una permutación tal que , o más formalmente, si hay una permutación tal que es una ventaja en si y solo if es una ventaja en . El problema del isomorfismo gráfico es el problema de...
Una aplicación importante del teorema de PCP es que produce resultados de tipo "dureza de aproximación". En algunos casos relativamente más simples, se puede demostrar tal dureza sin PCP. Sin embargo, ¿existe algún caso en el que el resultado de la dureza de la aproximación se haya probado por...
El teorema de PCP que no hay algoritmo de tiempo polinómico para MAX 3SAT para encontrar una asignación satisfacer cláusulas de una fórmula 3SAT satisfiable a menos que P = N P .7 / 8 + ε7/8+ϵ7/8+ \epsilonPAG= NPAGP=NPP = NP Existe un algoritmo de tiempo polinomial que satisface trivial de las...
¿Cómo se puede demostrar que relación existe entre "Conjetura de juegos únicos" y "Teorema de PCP"? ¿Cómo se explica "La conjetura de juegos únicos" es una forma más fuerte de "teorema de
El sistema de prueba probabilística se conoce comúnmente como una restricción de M A , donde Arthur solo puede usar f ( n ) bits aleatorios y solo puede examinar g ( n ) bits de el certificado de prueba enviado por Merlin (ver, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP...
El problema de mantenimiento de la orden (o "mantener el orden en una lista") es apoyar las operaciones: singleton: crea una lista con un elemento, le devuelve un puntero insertAfter: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo...
El teorema de la pretición paralela de Raz es un resultado importante en PCP, aproximación, etc. El teorema se resume de la siguiente manera. G=(S,T,A,B,π,V)G=(S,T,A,B,π,V)G=(\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B},\pi,
Estoy leyendo la prueba desde aquí y me topé con un problema técnico (pero crucial). Sé que esto es bastante específico y el contexto es problemático, pero no pude resolverlo yo mismo. En las páginas 51 y 55, después de presentar los verificadores "estándar", se vuelven a modificar los...
Una formulación equivalente del teorema de PCP es: para Max 3-SAT es -duro distinguir entre fórmulas satisfactorias y fórmulas donde, como máximo, la fracción r de las cláusulas es satisfactoria (para algunos r < 1 ).nortePAGNPNPrrrr < 1r<1r\lt 1 ¿Existe algún teorema de dicotomía...
Lo que sigue puede parecer estúpido (y eso probablemente refleja mi pobre comprensión, así que tengan paciencia conmigo) Tenía una consulta sobre el teorema de PCP. Sabemos que después de los primeros tres pasos a saber. Reducción de grados, expansión y amplificación de huecos , tenemos un gráfico...
En la mayoría de los sistemas de prueba probabilística (teorema PCP, por ejemplo), las probabilidades de error generalmente se definen del lado de los falsos positivos, es decir, una definición típica podría verse así: si , el verificador siempre acepta, pero en En otro caso, la probabilidad de...
El teorema de PCP establece que cada problema de decisión en NP tiene pruebas probabilísticamente comprobables (o de manera equivalente, que existe un sistema de prueba completo y cuasi-sonoro para teoremas en NP que usa complejidad de consulta constante y logarítmicamente muchos bits...
El libro de Arora y Barak contiene notas de capítulos sobre PCP Observamos que la estrategia general de Dinur recuerda en cierta medida la construcción en zig-zag de los gráficos de expansión y el algoritmo determinista de espacio de registro de Reingold para la conectividad no dirigida que se...
Estoy estudiando la Conjetura de juegos únicos y la famosa reducción a Max-Cut de Khot et al. Desde su artículo y en otras partes de Internet, la mayoría de los autores usan (lo que para mí es) una equivalencia implícita entre la reducción MAX-CUT y la construcción de pruebas particulares para...
¿Cuáles son los límites superiores asintóticos más conocidos en tamaños de pruebas probabilísticamente comprobables? Idealmente, estoy buscando una encuesta contemporánea sobre esta amplia pregunta, pero si no hay ninguna, estoy especialmente interesado en la inaccesibilidad de 3-SAT. Deje que 7/8...
En el paso de reducción de grados de la prueba de Dinur, el gráfico de entrada se transforma en un gráfico G ' reemplazando cada vértice v ∈ V ( G ) por un conjunto de vértices, c l o u d ( v ) , de modo que | c l o u d ( v ) | = d e g r e e G ( v ) , e imponiendo un gráfico expansor de grado d en...
Tengo algunas preguntas sobre la conjetura de Quantum PCP: ¿Cuál es la declaración de la conjetura de PCP cuántica? ¿Qué implicaciones tendría el teorema de PCP Quantum para la simulación de hamiltonianos? ¿Se cree que la adopción de la prueba de Irit Dinur del teorema clásico de PCP puede...
Se sabe que si PAGS= NPAGSP=NPP=NP entonces Co NPAGS= PCPAGS[ O ( l o g( n ) ) , O ( 1 ) ]CoNP=PCP[O(log(n)),O(1)]CoNP= PCP[O(log(n)),O(1)] . Además, se sabe que nortemiXPAGS= PCPAGS[ p o l y( n ) , p o l y( n ) ]NEXP=PCP[poly(n),poly(n)]NEXP=PCP[poly(n),poly(n)]. Parece que el PCP no puede...