Provas verificáveis probabilisticamente
Eu estou familiarizado com uma série de resultados que usam o teorema PCP (principalmente na aproximação de algoritmos), mas eu nunca me deparei com uma explicação clara do teorema PCP (ou seja, que ).NP=PCP(O(log(n)),O(1))NP=PCP(O(log(n)),O(1))\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1)) Quais...
Suponha que e G 2 sejam dois gráficos não direcionados no conjunto de vértices { 1 , … , n } . Os gráficos são isomórficos se e somente se houver uma permutação Π tal que G 1 = Π ( G 2 ) , ou mais formalmente, se houver uma permutação Π tal que ( i , j ) seja uma aresta em G 1 se e somente se ( Π (...
Uma aplicação importante do teorema do PCP é que ele produz resultados do tipo "dureza de aproximação". Em alguns casos relativamente mais simples, pode-se provar essa dureza sem o PCP. Existe, no entanto, algum caso em que a dureza do resultado da aproximação foi comprovada pela primeira vez...
O teorema do PCP afirma que não há algoritmo de tempo polinomial para o MAX 3SAT encontrar uma atribuição que satisfaça as cláusulas de 7/8 de uma fórmula 3SAT satisfatória, a menos que .P = N P7 / 8 + ε7/8+ϵ7/8+ \epsilonP= NPP=NPP = NP Existe um algoritmo de tempo polinomial trivial que satisfaz...
como mostrar que relação existe entre "conjectura de jogos únicos" e "teorema do PCP"? como explicar "conjectura de jogos únicos" é a forma mais forte de "teorema do
O sistema de prova probabilística é comumente referido como uma restrição de , onde Arthur pode usar apenas bits aleatórios e apenas examinar g (n) bits do certificado de prova enviado por Merlin (consulte http://en.wikipedia.org/wiki/Interactive_proof_system#PCP
O problema de manutenção de pedidos (ou "manutenção de pedidos em uma lista") é dar suporte às operações: singleton: cria uma lista com um item, retorna um ponteiro para ele insertAfter: dado um ponteiro para um item, insere um novo item depois dele, retornando um ponteiro para o novo...
O teorema da pretensão paralela de Raz é um resultado importante no PCP, na aproximação, etc. O teorema é resumido da seguinte forma. G = ( S, T, A, B, π, V)G=(S,T,UMA,B,π,V)G=(\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B},\pi, V)S, T, A,
Estou lendo a prova daqui e me deparei com um problema técnico (ainda que crucial). Eu sei que isso é bastante específico e o contexto é problemático, mas eu não consegui descobrir isso sozinho. Nas páginas 51 e 55, depois de apresentar os verificadores "padrão", eles se voltam para modificar os...
Uma formulação equivalente do teorema de PCP é: Para Max 3-SAT, é difícil distinguir entre fórmulas satisfatórias e fórmulas onde, no máximo, a fração das cláusulas é satisfatória (para alguns ).NPNPNPrrrr<1r<1r\lt 1 Existe algum teorema de dicotomia conhecido que classifique todo o CSP...
O que se segue pode parecer estúpido (e isso provavelmente reflete meu fraco entendimento - por isso, tenha paciência comigo) Eu tive uma consulta no teorema do PCP. Sabemos que após os três primeiros passos viz. Redução de Grau, Expansão e Amplificação de Gap, temos um gráfico de restrição com...
Na maioria dos sistemas de prova probabilística (teorema do PCP, por exemplo), as probabilidades de erro são geralmente definidas no lado dos falsos positivos, ou seja, uma definição típica pode parecer: se , o verificador sempre aceita, mas em outro caso, a probabilidade de rejeição é de pelo...
O Teorema do PCP declara que todo problema de decisão no NP tem provas probabilisticamente verificáveis (ou equivalentemente, que existe um sistema completo e quase sonoro para os teoremas do NP, usando complexidade de consulta constante e logaritmicamente muitos bits aleatórios). A “sabedoria...
O livro de Arora e Barak contém em notas de capítulo sobre PCP Observamos que a estratégia geral de Dinur lembra um pouco a construção em zigue-zague de gráficos expansores e o algoritmo determinístico de espaço de log determinante de Reingold para conectividade não direcionada descrito no...
Estou estudando a Conjectura de Jogos Exclusivos e a famosa redução para Max-Cut de Khot et al. Em seus artigos e em outros lugares da Internet, a maioria dos autores usa (o que para mim é) uma equivalência implícita entre a redução do MAX-CUT e a construção de testes específicos para códigos...
Quais são os limites superiores assintóticos mais conhecidos em tamanhos de provas probabilisticamente verificáveis? Idealmente, estou procurando uma pesquisa contemporânea sobre essa ampla questão, mas, se não houver, estou especialmente interessado na falta de aproximação do 3-SAT. Seja 7/8 +...
Na etapa de redução de grau da prova de Dinur, o gráfico de entrada é transformado em um gráfico substituindo cada vértice v \ in V (G) por um conjunto de vértices, nuvem (v) , de modo que | cloud (v) | = degree_G (v) e impondo um gráfico expansor de grau d na nuvem (v) para todos os v \ in V (G) ....
Tenho algumas perguntas sobre a conjectura do Quantum PCP: Qual é a afirmação da conjectura quântica do PCP? Que implicações o teorema do PCP quântico teria para simular Hamiltonianos? Acredita-se que a adoção da prova de Irit Dinur do teorema clássico do PCP provavelmente leve a uma prova da...
Sabe-se que se então . Além disso, sabe-se que . Parece que o PCP não pode nos dizer quais problemas naturais não estão no . Gostaria de saber se é possível usar a caracterização PCP para separar o do .C o N P = P C P [ O ( l o g ( n ) ) , O ( 1 ) ] N E X P = P C P [ p o l y ( n ) , p o l y ( n ) ]...