Teorema do PCP e complexidade da prova?

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 . $P=NP$ $CoNP= PCP[O(log(n)),O(1)]$ $NEXP=PCP[poly(n),poly(n)]$ $NP$ $CoNP$ $NP$

Quais são os melhores limites para a complexidade aleatória e a complexidade da consulta modo que o Problema Tautológico esteja no ? $r(n)$ $q(n)$ $PCP[O(r(n)),O(q(n))]$

cc.complexity-theory pcp proof-complexity Mohammad Al-Turkistany
fonte

Sabe-se que NEXP = PCP [poli (n), O (1)] como conseqüência do teorema do PCP. Veja, por exemplo, a introdução do artigo de Or Meir no FOCS 2009: sabedoria.weizmann.ac.il/~orm/papers/efficient_pcps_overview.pdf

Tsuyoshi Ito

Você mencionou a complexidade da prova no título (e nas tags originais). A complexidade computacional do problema de Tautologia está relacionada à complexidade da prova?

Tsuyoshi Ito

Sim, se P = CoNP, as Tautologias teriam provas curtas.

Mohammad Al-Turkistany

@Ito, a complexidade da prova geralmente estuda sistemas de prova que estabelecem tautologias proposicionais. Qualquer sistema de prova pode ser pensado como um algoritmo não determinístico para o problema de Tautologia. Prova de complexidade, então, é o estudo de algoritmos não determinísticos para o problema de Tautologia.

Iddo Tzameret 6/09/10

@Turkistany, você quis dizer NP = coNP.

Iddo Tzameret

Respostas:

Não são conhecidos resultados como . Infelizmente, separar e não é uma fruta baixa ... $coNP\not\subseteq PCP[o(n),q]$ $NP$ $coNP$

Dana Moshkovitz
fonte

Na verdade, acho que isso pode ser bom, e não infeliz. Se fosse tão simples separá-los, toda a comunidade pareceria muito tola por não tê-lo visto antes.

Joe Fitzsimons

Não é apenas que esses resultados não sejam conhecidos, eles provavelmente não são verdadeiros. Geralmente, pela mesma razão que acreditamos que acreditamos que o não determinismo não ajuda realmente na resolução de tautologias. Portanto, uma suposição natural é que o problema da tautologia não pode ser resolvido no tempo não determinístico (ou talvez nem no tempo ) o que implica que é não no .

c o N P \neq N P

$coNP \neq NP$

2^{n^{o (1)}}

$2^{n^{o(1)}}$

2^{o (n)}

$2^{o(n)}$

P C P [n^{o (1)}, p o l y (n)]

$PCP[n^{o(1)},poly(n)]$

Boaz Barak

@ Boaz, esta é uma boa resposta. Você poderia movê-lo e torná-lo uma resposta separada?

Mohammad Al-Turkistany

Penso que o seguinte artigo ajudará: Provas interativas polilogarítmicas por rodada para coNP colapsam a hierarquia exponencial

Ele afirma que , a menos que a hierarquia exponencial entre em colapso. ( é a classe de idiomas que possui provas interativas -move.) $\mathbf{coNP} \not\subset \mathbf{IP}[\log^{O(1)} n]$ $\mathbf{IP}[k]$ $k$

Em relação à relação natural entre provas interativas e probabilisticamente verificáveis, acho que o resultado acima deve ajudar.

Também sugiro dar uma olhada em Um novo protocolo de amostragem e aplicações para basear primitivas criptográficas na dureza de NP .

MS Dousti
fonte

Você poderia, por favor, elaborar a relevância do segundo artigo?

Iddo Tzameret

Uma introdução informal ao segundo artigo é apresentada aqui . A frase "Todos os sistemas de prova conhecidos (mesmo com vários provadores) para co-NP exigem provadores com complexidade de #P" é o cerne do que o relaciona à discussão atual.

MS Dousti