A conjectura do isomorfismo implica limites exponenciais inferiores na densidade das testemunhas?

O Isomorfismo conjectura de Berman e Hartmanis afirma que todos conjuntos são -completo tempo polinomial isomorfo para o outro. Isto significa que problemas -Complete são eficientemente redutível para o outro através de calculável tempo polinomial e bijeções inversíveis. A conjectura implica . $NP$ $NP$ $P\neq NP$

A conjectura isomorfismo implica um exponencial um limite inferior da densidade da conjuntos -Complete desde problema satisfiability é denso. Eu estou querendo saber se ele também implica uma exponencial um limite inferior da densidade de testemunhas para conjunto -completo. $NP$ $NP$

A conjectura do isomorfismo implica limites exponenciais inferiores na densidade das testemunhas? Implica que problemas -completo não pode estar em ? $NP$ $FewP$

O melhor resultado que estou ciente é o seguinte:

Se e então a conjectura do isomorfismo se mantém. $P=UP$ $NP=EXP$

Densidade de um conjunto refere-se ao número de cadeias de comprimento menor que no idioma. Um conjunto é exponencialmente denso se sua densidade for para alguns e para infinitamente muitos e esparsos se = . $D$ $S$ $n$ $S$ $D=\Omega(2^{n^\epsilon})$ $\epsilon \gt 0$ $n$ $D$ $O(poly(n))$

cc.complexity-theory structural-complexity Mohammad Al-Turkistany
fonte

Testemunhas densidade do conjunto

depende do número máximo de testemunhas para

sobre todo

X

$X$

x

$x$

x \in X

$x \in X$

Mohammad Al-Turkistany

Parece improvável. Seria interessante construir um oráculo onde a conjectura do isomorfismo se mantém e

... (Observe que fazer

pode tornar a vida um pouco mais difícil nessa construção, desde que, para obter a conjectura do isomorfismo, alguém precisaria de

, e ainda assim precisa de outra maneira de contornar a conjectura Joseph-Young.) #

N P = U P

$NP=UP$

N P = F e w P

$NP=FewP$

N P = U P

$NP=UP$

P \neq U P

$P \neq UP$

2100 Joshua Grochow

Respostas:

Não vejo como isso se seguiria imediatamente: a conjectura de isomorfismo é sobre linguagens e não parece ter implicações sobre a estrutura de testemunhas dos verificadores NP. (Todo idioma possui infinitos verificadores diferentes para isso, e você pode potencialmente manipular esses verificadores para fazer coisas estranhas.)

Mas sua pergunta revela outra pergunta intrigante muito natural, sobre o seguinte fortalecimento da conjectura de isomorfismo:

"Todos os verificadores de conjuntos NP completos são poli-tempo isomórficos?"

$\phi_{L,L'}$ $L,L'$ $V,V'$ $\psi_{V,V'}$ $\phi_{L,L'}$ $NP$ as provas de dureza em que consigo pensar também fornecem uma correspondência individual desse tipo. Essa "conjectura de isomorfismo de testemunha" mais forte implicaria algum tipo de resposta sim à sua pergunta.

Uma pesquisa rápida no Google (digitando 'conjectura de isomorfismo de testemunha') encontrou uma pesquisa de algumas abordagens para esse tipo de pergunta:

Eric Allender. Investigações sobre a estrutura de conjuntos completos. Perspectivas da complexidade computacional: o volume do aniversário de Somenath Biswas, Springer, 2014

Ryan Williams
fonte

+1 muito interessante. Seguindo sua sugestão, pesquisei no Google e encontrei este artigo, reduções isomórficas de testemunhas e o problema de busca local . Esse é o tipo de isomorfismo de testemunha necessário ?

Mohammad Al-Turkistany

L, L^{'}

$L,L'$

N P

$\mathsf{NP}$

V, V^{'}

$V,V'$

ϕ_{L, L^{'}}, ψ_{V, V^{'}}

$\phi_{L,L'}, \psi_{V,V'}$

V, V^{'}

$V,V'$

V

$V$

V^{'}

$V'$

{{0, 1}^{n} w | V (w) = 1}

$\{\{0,1\}^n w | V(w)=1\}$

Certo, você deve ter cuidado ao formular a conjectura para evitar contra-exemplos triviais. Googling me revelou que eu não sou o primeiro, então eu sugiro a leitura do trabalho de pessoas que têm pensado sobre isso por mais de 10 minutos :)

Ryan Williams

Ryan, acho que sua conjectura é muito importante. Pode ser mais fácil provar do que a conjectura padrão de isomorfismo de Berman e Hartmanis. Eu acho que sua conjectura sugere a existência de verificador universal para todos os conjuntos NP.

Mohammad Al-Turkistany