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?)
Em palavras, quais seriam as consequências de e ?P ≠ N P
cc.complexity-theory
complexity-classes
conditional-results
polynomial-hierarchy
Xavier Labouze
fonte
fonte
Respostas:
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?")N P = c o N P
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 .N P = c o N P
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.P≠NP=coNP
fonte
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=BPP P NP=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:B P P ≠ P N P =co N P . 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 P ≠ P , 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 - PE ≠ N E P H P B P P = P B P P ≠ P P N P =co N P P H = N P N P - P . Finalmente, a presença de uma linguagem de contagem em é bem conhecido para implicar E ≠ N E .N P - P E ≠ N E
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 P ≠ P , como este último por si só não é conhecido implicar E ≠ N E . Esta "anomalia" parece apoiar a conjectura B P P = P .N P =co N P B P P ≠ P E ≠ N E B P P = P
fonte
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.V a l i a n t′s - D e fi n i t i o n :----------------------- C # C= ∪A ∈ C( # P)UMA ( # PUMA) UMA
Pela definição de Valiant, já temos# N P = # C o N P
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(|T o d um′s - D e fi n i t i o n :--------------------- C # . C f C- R p x e 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 .# . N P = # . C o N P N P = C o N P
Então, se nós também assumimos que então teríamos F P ≠ # P .P ≠ N P F P ≠ # P
fonte
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)".
fonte