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

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.

cc.complexity-theory reference-request complexity-classes conditional-results polynomial-hierarchy András Salamon
fonte

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

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 P

L

$L$

^{O}

$^O$

O

$O$

^{O}

$^O$

^{O}

$^O$

L

$L$

⟹ L \in

$\implies L \in$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

(O (\log \log n), p o l y)

$(O(\log \log n), \rm{poly})$

\subseteq

$\subseteq$

^{{m o d}_{q} P}

$^{\rm{mod}_q \rm{P}}$

q

$q$

^{O}

$^O$ = NP dá um novo limite superior em H. É aberto se H = PH).

^{O}

$^O$

Russell Impagliazzo

@ Russell: obrigado! Esse comentário parece uma resposta.

András Salamon

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-8

H

$H$

Joshua Grochow 8/13

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:

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. $\mathsf{P}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{H}$ $L$ $\mathsf{H}$ $L$ $\mathsf{P}^O$ $O$ $\mathsf{P}^O=\mathsf{NP}^O$ $L$ $\mathsf{H}$ $\mathsf{P}=\mathsf{NP} \implies L\in\mathsf{P}$ $\mathsf{PH} \subseteq \mathsf{H} \subseteq \mathsf{AltTime}(O(\lg\lg n),\mathsf{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 . $\mathsf{H} \subseteq \mathsf{P}^{\mathsf{mod}_q \mathsf{P}}$ $q$ $\mathsf{P}^O=\mathsf{NP}^O$ $\mathsf{H}$ $\mathsf{H}=\mathsf{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 . $f(n)$ $\mathsf{H}$ $\mathsf{AltTime}(f(n),\mathsf{poly})$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}=\mathsf{AltTime}(f(n),\mathsf{poly})$ $\mathsf{NP}$ $\mathsf{L}$

Para definição de veja a definição 6.3 em $\mathsf{H}$

Kenneth W. Regan, " Conjuntos de índices e apresentações de classes de complexidade ", 1999

Kaveh
fonte

f (n) = \lg \lg n

$f(n) = \lg \lg n$

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

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

P^{O} = N P^{O}

$P^O = NP^O$

L

$L$

L

$L$

O

$O$

O

$O$

P^{O} \neq N P^{O}

$P^O \neq NP^O$

L

$L$

O

$O$

2^{Σ^{*}}

$2^{\Sigma^*}$

Joshua Grochow

$\Sigma^P_k$ $k$

$M$ $x$ $y$ $\mathsf{NP}$

$Cook(M, \vec{n}, t)$ $M$ $s(\vec{n},t) \in \mathsf{poly}$ $M$ $\vec{n}$ $t$

$\mathsf{P}=\mathsf{NP}$ $A$ $p\in\mathsf{poly}$

$s_i$ $i$ $s_{i+1} = s\circ p(s_i)$ $k$ $q(n) = (s \circ p)^k(n)$ $n$ é o tamanho da fórmula TQBF fornecida como entrada.

$k$ $q(n) \in \mathsf{poly}$ $\mathsf{P}$

$k \in \omega(1)$ $q(n)$ $n^{2^{O(k)}}$ $k = \lg \lg n$ $k = \lg n$

$C$

T ⊢ P = N P \to P = C

$T \vdash \mathsf{P} = \mathsf{NP} \to \mathsf{P}=C$

T

$T$

Z F C

$\mathsf{ZFC}$

P \neq N P

$\mathsf{P} \neq \mathsf{NP}$

$C$ $\mathsf{H}$ $\mathsf{H}$ $\mathsf{P}$ $\mathsf{P}=\mathsf{NP}$

$\mathsf{BPP} = \mathsf{PP}$ $\mathsf{IP} = \mathsf{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