Pode-se amplificar P = NP além de P = PH?

54

Em Complexidade Descritiva , Immerman tem

Corolário 7.23. As seguintes condições são equivalentes:
1. P = NP.
2. Sobre estruturas finitas e ordenadas, FO (LFP) = SO.

Isso pode ser pensado como "amplificando" P = NP para uma declaração equivalente sobre classes de complexidade (presumivelmente) maiores. Observe que SO captura a hierarquia de tempo polinomial PH e que FO (LFP) captura P, então isso pode ser considerado como P = NP se P = PH.

(A parte interessante disso é a afirmação de que P = NP implica P = PH; é trivial que P = CC implique P = NP para qualquer classe CC que contenha NP. Immerman simplesmente observa "se P = NP então PH = NP" , presumivelmente porque P = NP pode ser usado com a definição oracle de PH para mostrar indutivamente que toda a hierarquia entra em colapso.)

Minha pergunta é:

Quanto mais P = NP pode ser amplificado dessa maneira?

Em particular, qual é a maior classe conhecida CC 'tal que P = NP implica P = CC', e a menor classe CC tal que P = NP implica CC = NP? Isso permitiria que P = NP fosse substituído pela pergunta equivalente CC = CC '. P parece ser uma classe bastante poderosa, que parece fornecer pouco "espaço de manobra" para argumentos que tentam separá-lo de NP: até que ponto a sala de manobra pode ser amplificada?

É claro que eu também estaria interessado em um argumento que mostra que P = PH é o limite dessa abordagem.


Editar: observe a questão intimamente relacionada Por que P = NP não implica P = AP (ou seja, P = PSPACE)? que se concentra na outra direção, por que não temos provas de que P = PSPACE. As respostas de Kaveh e Peter Shor argumentam que o número de alternâncias sendo corrigidas é fundamental. Outra questão relacionada é um problema de decisão que não se sabe estar em PH, mas estará em P se P = NP, que pede um problema candidato; as respostas também podem ser usadas para construir respostas para essa pergunta, embora essas classes sejam um pouco artificiais (obrigado a Tsuyoshi Ito por apontar isso). Em um cenário mais geral, colapso da máquina de turing limitada por exptime e alternância pergunta se um colapso local em qualquer nível de uma hierarquia de alternância induz um colapso ascendente, como acontece com a hierarquia de tempo polinomial.

András Salamon
fonte
12
Relacionado (autopromoção desavergonhada): Um problema de decisão que não se sabe estar na HP, mas estará em P se P = NP .
Tsuyoshi Ito
17
Como forma de formalizar quais idiomas estão em P se P = NP, Regan introduziu a classe de complexidade H. Uma linguagem está em H se e somente se L está em P relação a todo oráculo modo que P = NP . Assim, está em H se a afirmação P = NP P relativizada. PH H alternado . Do teorema de Toda, e alguns dos lemas do teorema de Toda, também é verdade que H P para cada . (Basicamente, qualquer oráculo que satisfaça PO O O O LLOOOOL( S ( log log n ) , p o l y ) m o d Q P Q O óL(O(loglogn),poly)modqPqO = NP dá um novo limite superior em H. É aberto se H = PH).O
Russell Impagliazzo
4
@ Russell: obrigado! Esse comentário parece uma resposta.
András Salamon
5
Finalmente, encontrei uma referência à classe Ken Regan : consulte a definição 6.3 de "Conjuntos de índices e apresentações de classes de complexidade", disponível em: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8927 . Versão oficial em: dx.doi.org/10.1016/0304-3975(95)00146-8H
Joshua Grochow 8/13
3
Seja f (n) qualquer função ilimitada. H não está contido no tempo de alternância (f (n), poli) e se você puder provar que P = NP implica P = tempo de alternância (f (n), poli), então NP é diferente de L.
Lance Fortnow

Respostas:

6

Do comentário de Russell Impagliazzo :

Como forma de formalizar quais idiomas estão em se , Regan introduziu a classe de complexidade . Uma linguagem é em se e somente se é em em relação a toda a Oracle modo que . Portanto, está em se a instrução relativizada. P = N P H L H L P O O P O = N P O L H P = N PPP=NPHLHLPOOPO=NPOLHP=NPLPPHHAltTime(O(lglgn),poly). Do teorema de Toda, e alguns dos lemas do teorema de Toda, também é verdade que para cada . Basicamente, qualquer oráculo que satisfaça fornece um novo limite superior em . Está aberto se .HPmodqPqPO=NPOHH=PH

E do comentário de Lance Fortnow :

Seja qualquer função ilimitada. não está contido em e se você puder provar implica então é diferente de .H A l t T i m e ( f ( n ) , p o l y ) P = N P P = A l t T i m e ( f ( n ) , p o l y ) N P Lf(n)HAltTime(f(n),poly)P=NPP=AltTime(f(n),poly)NPL

Para definição de veja a definição 6.3 emH

Kaveh
fonte
11
f(n)=lglgn
3
Estou confuso sobre alguma coisa. Por que a resposta de Josh Grochow à pergunta anterior sobre esse tópico ( cstheory.stackexchange.com/a/2039/1575 ) também responde essencialmente à pergunta de Regan? Ou seja, por que não dá um exemplo de uma linguagem L que está em P se P = NP por um argumento relativizante, mas que não está em PH se P! = NP? E por que, portanto, não mostra que, se P! = NP, H é estritamente maior que PH?
21816 Scott Aronson
3
Na verdade, uma resposta possível me ocorre. A questão é que, na construção de Grochow, a própria definição da linguagem L dependerá do oráculo O?
Scott Aaronson
11
PO=NPOLLOOPONPOLO2Σ
Joshua Grochow
5

ΣkPk

MxyNP

Cook(M,n,t)Ms(n,t)polyMnt

P=NPAppoly

siisi+1=sp(si)kq(n)=(sp)k(n)n é o tamanho da fórmula TQBF fornecida como entrada.

kq(n)polyP

kω(1)q(n)n2O(k)k=lglgnk=lgn


C

TP=NPP=C
TZFCPNP

CHHPP=NP


BPP=PPIP=PSpace

Também acho que há apenas uma maneira correta de relativizar uma classe de complexidade problemática que causa muitos conceitos errôneos (como pensar a relativização como uma operação funcional em classes de complexidade em seu sentido extensional, uma relativização é uma modificação de um modelo de computação , não uma classe de funções ou idiomas). Eu acho que visualizar relativizações como estruturas de computação modificadas (interativas) é mais útil. Dessa forma, existem muitas maneiras úteis de relativizar as classes de complexidade (no sentido intencional). Para obter qualquer informação sobre a configuração não relativizada de uma estrutura relativizada, precisamos de algum tipo de princípio de transferência semelhante ao princípio de transferência na análise não-padrão. Observe que escolher um método particular de relativização para classes que preserva as relações conhecidas entre classes não nos dá um princípio de transferência (este é o principal critério normalmente usado na literatura para decidir qual é "a" relativização correta de uma classe).

Kaveh
fonte
Eu concordo com "visualizar relativizações como uma estrutura de computação interativa é mais útil na minha opinião" de uma certa maneira. Nomeadamente, a apresentação de relativizações poderia ser mais intuitiva de entender, começando com a situação em que a (s) máquina (s) (com acesso interativo ao oráculo) é dada primeiro e um oponente pode selecionar um idioma para o oráculo. Em seguida, muda-se para a situação em que uma linguagem (complexa) do oráculo é dada primeiro, e as máquinas agora podem ser adaptadas ao mundo dado pelo oráculo específico.
Thomas Klimpel