vs

15

Em nosso trabalho recente, resolvemos um problema computacional que surgiu no contexto combinatório, pressupondo que , ondeEXPEXP é aversão E X P deEXPEXP . O único artigo sobreP que encontramos foi o artigo de Beigel-Buhrman-Fortnow, de1998,citado noComplexity Zoo. Entendemos que podemos ter versões paritárias deproblemascompletosde N E X P (consulteesta pergunta), mas talvez muitos deles não sejam completos emEXPNEXP . EXP

PERGUNTA: Existem razões de complexidade para acreditar que ? Existem problemas combinatórios naturais que são completos emEXPEXP ? Existem algumas referências que podem estar faltando? EXP

Igor Pak
fonte
6
Eu acho que as versões de paridade de pelo menos alguns problemas completos do NEXP seriam completas pelo mesmo motivo, por exemplo, SUCCINCT 3SAT. Aulas de paridade são `` sintática" tal como existencial não-determinismo, então você tem os mesmos métodos padrão para tornar problemas completos.
Greg Kuperberg
Obrigado, Greg. Compreendo. Porém, nem todos os problemas funcionam, por exemplo, a paridade do número de três cores dos gráficos SUCCINCT é fácil.
Igor Pak
2
A questão em seu exemplo da paridade do número de três cores (que obviamente é divisível por 6) é ortogonal à questão declarada das classes de complexidade no nível EXP. A questão é se há uma redução parcimoniosa, ou seja, uma redução que preserva o número de testemunhas. Isso é conhecido com frequência, mas às vezes não. Por exemplo, no caso de três cores, há um belo artigo de Barbanchon (que eu vi recentemente por minhas próprias razões) que dá uma redução parcimoniosa do SAT, exceto pelo fator 6.
Greg Kuperberg
2
Ah, certo. Interessante. Encontrado: Régis Barbanchon, No gráfico único de 3 cores e reduções parcimoniosas no avião (2004).
Igor Pak
3
@ GregKuperberg: Parece uma resposta! Observe que Valiant mostrou ( people.seas.harvard.edu/~valiant/focs06.pdf ) que mesmo é P completo. 2SATP
Joshua Grochow 17/05

Respostas:

14

Em termos de razões de complexidade (em vez de problemas completos): O Hartmanis-Immerman-Sewelson Teorema também deve funcionar, neste contexto, a saber: sse existe um conjunto polinomialmente escasso em PP . Dado o quão distantes pensamos que P e P estão - por exemplo, Toda mostrou que P HB P P P - seria bastante surpreendente se não houvesse conjuntos esparsos em suas diferenças.EXPEXPPPPPPHBPPP

Mais diretamente, se não houvesse conjuntos esparsos em suas diferenças, diria que para todo verificador , se o número de cadeias de comprimento n com um número ímpar de testemunhas for limitado por n O ( 1 )NPnnO(1) , então o problema [ de dizer se existe um número ímpar de testemunhas] deve estar em . Isso parece um fato bastante impressionante e improvável.P

Joshua Grochow
fonte
Eu não entendo a última parte. Qualquer problema de PN pode ser expresso de tal maneira que o número de testemunhas seja sempre uniforme e 0 seja polinomialmente limitado; portanto, você está efetivamente dizendo que P = NP e não vejo como isso se segue.
Emil Jeřábek apoia Monica
1
@Emil, o "verificador" entre parênteses parece esclarecer o que Josh quis dizer.
Kaveh
@ EmilJeřábek: De fato, Kaveh entendeu exatamente. Como você ressalta, a declaração realmente funciona se você falar sobre todos os verificadores de NP, e não sobre todos os problemas de NP. Eu editei a resposta para que este não seja mais um comentário entre parênteses.
Joshua Grochow
Desculpe, mas isso não esclareceu nada. Se a declaração se aplica a todos os verificadores, ela se aplica em particular aos verificadores que sempre têm um número par de testemunhas.
Emil Jeřábek apoia Monica
1
@ EmilJeřábek: Ah, sim, vejo sua confusão agora (eu acho). Esclarecido. O resultado parece um pouco menos impressionante para mim, mas não muito (especialmente a luz do resultado de Toda).
Joshua Grochow