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

8

O Isomorfismo conjectura de Berman e Hartmanis afirma que todos conjuntos são -completo tempo polinomial isomorfo para o outro. Isto significa que N P 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 P N P .NPNPPNP

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 N P conjunto -completo.NPNP

A conjectura do isomorfismo implica limites exponenciais inferiores na densidade das testemunhas? Implica que problemas -completo não pode estar em F e w P ?NPFewP

O melhor resultado que estou ciente é o seguinte:

Se e N P = E X P, então a conjectura do isomorfismo se mantém.P=UPNP=EXP

Densidade de um conjunto S refere-se ao número de cadeias de comprimento menor que n no idioma. Um conjunto S é exponencialmente denso se sua densidade for D = Ω ( 2 n ϵ ) para alguns ϵ > 0 e para infinitamente muitos n e esparsos se D = O ( p o l y ( n ) ) .DSnSD=Ω(2nϵ)ϵ>0nDO(poly(n))

Mohammad Al-Turkistany
fonte
Testemunhas densidade do conjunto depende do número máximo de testemunhas para x sobre todo x X . XxxX
Mohammad Al-Turkistany
Parece improvável. Seria interessante construir um oráculo onde a conjectura do isomorfismo se mantém e ou N P = F e w P ... (Observe que fazer N P = U P pode tornar a vida um pouco mais difícil nessa construção, desde que, para obter a conjectura do isomorfismo, alguém precisaria de P U P , e ainda assim precisa de outra maneira de contornar a conjectura Joseph-Young.) #NP=UPNP=FewPNP=UPPUP
2100 Joshua Grochow

Respostas:

14

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?"

ϕL,LL,LV,VψV,VϕL,LNPas 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
+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
5
L,LNPV,VϕL,L,ψV,VV,VVV{{0,1}nw|V(w)=1}
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