Consequências da

12

Sabemos que se , todo o PH entra em colapso. E se a hierarquia polinomial entrar em colapso parcial? (Ou como entender que o PH poderia entrar em colapso acima de um certo ponto e não abaixo?)P=NP

Em palavras, quais seriam as consequências de e ?P N PNP=coNPPNP

Xavier Labouze
fonte
3
Nesse caso, o PH ainda entra em colapso (para o 1º nível e não o 0º nível).
Huck Bennett
A primeira frase parece expressar que "estamos com problemas se P = NP não ocorre porque a hierarquia entra em colapso", o que não está correto (deixando de lado a questão possivelmente controversa de saber se P = NP é uma situação problemática ou não).
Kaveh
2
@ Huck, acho que o OP pode estar tentando perguntar quais são as consequências do colapso do PH no 1º nível. Que problemas legais poderíamos resolver então?
Artem Kaznatcheev
@ Xavier: Por que você diz "... e estamos com problemas" . P = NP, eo consequente colapso PH, seria simplesmente fantástico ;-)
Giorgio camerani
@ArtemKaznatcheev: tks ao seu comentário comentário
Xavier Labouze

Respostas:

17

Para mim, uma das conseqüências mais básicas e surpreendentes de é a existência de provas curtas para toda uma série de problemas em que é muito difícil ver por que eles deveriam ter provas curtas. (Isso é como dar um passo atrás de "Que outras implicações de complexidade esse colapso tem?" Para "Quais são as razões básicas e práticas que esse colapso seria surpreendente?")NP=coNP

Por exemplo, se , em seguida, para cada gráfico que não é Hamiltoniano, existe uma pequena prova de que fato. Da mesma forma, para gráficos que não são de 3 cores. Da mesma forma, para pares de gráficos que não são isomórficos. Da mesma forma para qualquer tautologia proposicional .NP=coNP

Em um mundo em que , a dificuldade em provar tautologias proposicionais não é que algumas tautologias curtas tenham provas longas - porque nesse mundo toda tautologia tem uma prova polinomialmente curta - mas sim que há algumas outro motivo pelo qual não conseguimos encontrar essas provas com eficiência.PNP=coNP

Joshua Grochow
fonte
Eu gosto desta resposta! +1
Tayfun Pago 15/02
Obrigado pela sua resposta, a consequência sublinhada é bastante surpreendente. Eu me pergunto que tipo de outro motivo não consegue encontrar essas provas com eficiência. Qualquer ideia ?
Xavier Labouze
12

Se também assumirmos , a hipótese também causaria o colapso de classes aleatórias:NP=RP . Embora todos sejam conjecturados para entrar em colapso incondicionalmente em P , ainda está em aberto se isso realmente acontece. Em qualquer caso, N P = C O N P não parecem implicar em si mesmo que estas classes randomizados colapso.ZPP=RP=CoRP=BPPPNP=coNP

Se não tiverem, ou seja, temos pelo menos , então, junto apenas com a hipótese N P = c o N P , isso teria outra consequência importante:BPPPNP=coNP . Isto decorre de um resultado de BABAI, Fortnow, Nissan e Wigderson, que diz que, se todos os (Tally) linguagem unária em P H cair em P , então B P P = P . Assim, se B P PP , então eles podem não toda a queda em P , como o N P = C O N P pressuposto implica P H = N P . Portanto, deve haver uma linguagem de registro em N P - PENEPHPBPP=PBPPPPNP=coNPPH=NPNP-P. Finalmente, a presença de uma linguagem de contagem em é bem conhecido para implicar EN E .NP-PENE

As mostras de raciocínio acima do efeito interessante que o hipótese de, apesar de ser um colapso, na verdade, amplifica a separação poder de B P PP , como este último por si só não é conhecido implicar EN E . Esta "anomalia" parece apoiar a conjectura B P P = P .NP=coNPBPPPENEBPP=P

Andras Farago
fonte
1
Talvez eu esteja demorando aqui, mas como NP = coNP implica ZPP = RP = coRP = BPP?
Joshua Grochow
@JoshuaGrochow Também estou preso nisso.
Tayfun Pay
Obrigado, eu realmente perdi uma condição. Eu corrigi a resposta.
Andras Farago 15/02
@AndrasFarago okay! 1)
Tayfun Pay
@AndrasFarago Tks pela sua resposta!
Xavier Labouze
7

Há duas definições para a contagem aulas além . Um foi definido por Valiant e o outro por Toda.#P

Para qualquer classeC, definir#C= Um C (#P) A , em que( # P A), as funções contando os caminhos aceitáveis ​​das máquinas de Turing de tempo polinomial não determinístico comAcomo seu oráculo.VumaeuEuumants-DefEunEutEuon:_C#C=UMAC(#P)UMA(#PUMA)UMA

Pela definição de Valiant, já temos #NP=#CoNP

Para qualquer classeC, definir#. Cser a classe de funçõesftal que para algunsC-computável com dois argumentos predicadoRe alguns polinomialp, para cada cordaxque afirma que:f(x)=| | {y| p(|Todumas-DefEunEutEuon:_C#.CfC-Rpxe R ( x , y ) } | | .f(x)=||{y|p(|x|)=|y|R(x,y)}||

Pela definição de Toda, temos se e somente se N P = C O N P .#.NP=#.CoNPNP=CoNP

Então, se nós também assumimos que então teríamos F P# P .PNPFP#P

Tayfun Pay
fonte
É a versão contadora do NP.
Tayfun Pay
A que se refere o período em "# .NP"?
Timothy Sun
4
Existem dois tipos se contar hierarquias definidas. Um de Valiant em 1979 e ele usa a notação #P, # NP, # Co-NP ... Onde # NP = Co-NP. Por outro lado, Toda definiu uma hierarquia diferente. E a notação para isso usa pontos. E # .NP! = #. Co-NP, a menos que NP = Co-NP #
Tayfun Pay
2

Ker-i Ko Mostrou que existe um oráculo que faz o colapso do PH no k-ésimo nível. Ver "Ker-I Ko: Hierarquias Polinomiais Relativizadas do Tempo com Níveis Exatamente K. SIAM J. Comput. 18 (2): 392-408 (1989)".

Bin Fu
fonte
Você pode nos vincular ao jornal?
Tayfun Pay
@ BinFu Tks - Pensei que PH cai no primeiro nível ...
Xavier Labouze
1
Para o caso k = 1, é o caso deste problema. O tempo polinomial diminui para NP na condição NP = coNP. A existência do oráculo para o nível k-ésimo no artigo de Ko significa a barreira de qualquer método relativizado para lidar com o problema de colapso do PH.
Bin Fu
1
@BinFu: suas observações não descrevem nenhuma consequência de PNP = coNP . A questão não era como mostrar um colapso no primeiro nível, ou sobre resultados que também descrevem um colapso no primeiro nível, mas o que seria conhecido como corolário de um colapso no primeiro nível. Não vejo como sua resposta tenha isso.
Niel de Beaudrap
1
Toda fórmula booleana satisfatória possui uma prova polinomial de tempo e duração, que são as atribuições de verdade para tornar a fórmula verdadeira. A condição NP = coNP faz com que todas as fórmulas booleanas insatisfatórias tenham uma prova polinomial de tempo e duração. Se P não for igual a NP e NP = coNP, não haverá algoritmo de tempo polinomial para encontrar a prova de comprimento polinomial para uma fórmula booleana por sua satisfação ou insatisfação. Da mesma forma, teremos conclusões semelhantes para todos os problemas no PN.
Bin Fu