Um problema de decisão que não se sabe estar em PH, mas estará em P se P = NP

Editar : Como Ravi Boppana corretamente apontou em sua resposta e Scott Aaronson também acrescentou outro exemplo em sua resposta , a resposta a essa pergunta acabou sendo "sim" de uma maneira que eu não esperava. Primeiro, pensei que eles não responderam à pergunta que eu queria fazer, mas, depois de pensar um pouco, essas construções respondem a pelo menos uma das perguntas que eu queria fazer, ou seja: “Existe alguma maneira de provar um resultado condicional? P = NP ⇒ L ∈P 'sem provar o resultado incondicional L ∈PH? ”Obrigado, Ravi e Scott!

Existe um problema de decisão L tal que as seguintes condições sejam atendidas?

L não é conhecido por estar na hierarquia polinomial.
Sabe-se que P = NP implicará L ∈P.

Um exemplo artificial é tão bom quanto um exemplo natural. Além disso, embora eu use a letra " L ", pode ser um problema de promessa em vez de um idioma, se ajudar.

Background . Se sabemos que um problema de decisão L está na hierarquia polinomial, sabemos que “P = NP ⇒ L ∈P”. A intenção da pergunta é perguntar se o inverso é válido. Se existir um idioma L que satisfaça as duas condições acima, ele pode ser considerado uma evidência de que o inverso falha.

A pergunta foi motivada pelo interessante comentário de Joe Fitzsimons à minha resposta à pergunta de Walter Bishop, “ Consequências de #P = FP ”.

cc.complexity-theory conditional-results np polynomial-hierarchy Tsuyoshi Ito
fonte

Provar um negativo universal é sempre difícil, mas eu ficaria surpreso se esse idioma existisse. A conjectura linial-nisana generalizada (se tivesse acabado verdade) não teria implícito o que você está perguntando, eu não acredito. Significaria apenas que o BQP não estava contido no PH. Se o PH desmoronasse para P, o BQP ainda não estaria contido em P (H).

Daniel Apon

Você está perguntando se existe uma classe de complexidade X st X não é um subconjunto de PH e P = NP -> X = P?

Philip White

@ Philip: Sim, mas não acho que isso mude o problema, porque geralmente podemos converter um problema de decisão L em uma classe X de problemas de decisão redutíveis a L. Pelo menos essa era minha intenção de fazer essa pergunta em termos de problemas de decisão .

Tsuyoshi Ito

Talvez você queira exigir que o idioma esteja de alguma forma próximo ao PH, além de seus requisitos atuais? Talvez, digamos, no PSPACE (embora seja discutível a proximidade do PSPACE com PH; ver S. Fenner, S. Homer, M. Schaefer, R. Pruim. Hierarquias hiper-polinomiais e o salto polinomial. 2001), pp. 241-256 cse.sc.edu/~fenner/papers/hyp.pdf ). Ou talvez você realmente queira solicitar uma linguagem natural desse tipo.

L

$L$

Joshua Grochow 8/10/10

@ Josué: Obrigado pelo comentário e pela referência. Conforme declarado na atualização (revisão 3), agora acho que fiz a pergunta certa (ao contrário do que adicionei na revisão 2). Eu queria saber “Existe alguma maneira de provar um resultado condicional 'P = NP ⇒ L∈P' sem provar o resultado incondicional L∈PH?” Para esse propósito, a naturalidade do problema não deve ser exigida porque, uma vez lá é um método de prova, deve aplicar-se igualmente a exemplos naturais e artificiais.

Tsuyoshi Ito

Respostas:

Como você não se importa com uma linguagem artificial, que tal definir como vazio se P for igual a NP e como o Problema de Parada se P não for igual a NP. Ok, é meio trapaceiro, mas acho que você precisará reformular o problema para evitar esses truques. $L$

Ravi Boppana
fonte

Obrigado, vejo o ponto (defina L = {M: A máquina de Turing M pára e P P NP}). Obviamente, isso não responde ao que eu queria perguntar, mas acho que preciso pensar mais para formular a pergunta que queria fazer corretamente.

Tsuyoshi Ito

Se um exemplo artificial é realmente tão bom quanto um exemplo natural, posso realmente fornecer um exemplo!

Edit: Além disso, meu exemplo é "um pouco" menos trapaceiro do que o sugerido por Ravi Boppana (onde consideramos L como o idioma vazio se P = NP e o problema de parada do contrário), pois definirei o idioma L, fornecendo um procedimento finito para decidir se L para qualquer entrada x. Em nenhum momento será decidido se x∈L requer a solução de uma questão matemática "ilimitada", como P vs. NP. $x \in$

Sem mais delongas: deixar ser uma enumeração de máquinas polytime Turing. Para todos os , deixar ser o primeiro lexicograficamente que decide correctamente 3SAT em todas as entradas de comprimento ou menos. Em seguida, defina a linguagem L da seguinte maneira: para todas as entradas de tamanho , L se e somente se a máquina de Turing codificada por parar no máximo $M_1, M_2, ...$ $n$ $M_{t(n)}$ $M_i$ $n$ $x$ $n$ $x \in$ $x$ $n^{t(n)}$ etapas quando executado em uma fita em branco.

Reivindicação 1: Se P = NP, então L P. $\in$

Prova: Se P = NP, então há alguns fixo que resolve 3SAT para todas as entradas; portanto para todos os . QED $M_i$ $t(n) \le i$ $n$

Reivindicação 2: Se P NP, então L P. $\ne$ $\notin$

Prova: Se aumenta sem limite, podemos simplesmente aplicar o Teorema da Hierarquia de Tempo. QED $t(n)$

Agora, L não está apenas em P assumindo P NP: presume-se que não estaria em PH (ou mesmo no PSPACE)! $\ne$

Aliás, eu me pergunto se alguém pode melhorar a construção acima, para obter uma linguagem L que está em P se P = NP, mas provavelmente não em PH ou PSPACE se P NP? $\ne$

Scott Aaronson
fonte

Obrigado! Não fui capaz de modificar a construção para tornar possível a não associação ao PH, mas isso é suficiente para me convencer de que adicionar a condição de que L é decidível com uma prova construtiva da decidibilidade provavelmente não mudará muito a situação. Hmm.

Tsuyoshi Ito

Aceitarei a resposta de Ravi Boppana porque foi a primeira a chegar, embora eu queira aceitar as duas porque ambas me deram mais entendimento sobre o problema. Espero que você entenda ....

Tsuyoshi Ito

Agradável. Esta é uma ótima resposta.

Daniel Apon 9/10/10

@ Tyson Williams: Caso você não tenha percebido, tenha muito cuidado para não introduzir um erro ao editar uma postagem por outros usuários. Foi uma sorte que Joe notou e o corrigiu.

Tsuyoshi Ito

Respondendo a pergunta de Scott Aaronson, mas um pouco demasiado tempo para um comentário, aqui é uma construção de uma linguagem tal que implica , mas implica . $L$ $P = NP$ $L \in P$ $P \neq NP$ $L \notin PH$

$M_1, M_2, M_3, \dotsc$ $t(n)$ $L$ $\Sigma_{k} SAT$ $k$ $t(n) \to \infty$ $P \neq NP$ $s=(i,j)$ $\Sigma^* \to \Sigma^* \times \Sigma^*$ $M_i$ $L$ $\Sigma_{j} SAT$ $n_{s}$ $t(n_{s}) > t(n_{s-1})$ $n_{0} = 1$ $n_{s}$ $L(1^{n_{s}}) = 1 - \Sigma_{k}SAT(M_{i}(1^{n_{s}}))$ $n_{s}$ $L$

$P \neq NP$ $t(n) \to \infty$ $n \to \infty$ $n_{s}$ $L$ $PH$ $P = NP$ $L$ $L$ $P$

Joshua Grochow
fonte

n_{s}

$n_s$

n_{s}

$n_s$

s

$s$

1^{n}

$1^n$

n

$n$

n_{s}

$n_s$

s

$s$

s

$s$

1^{n}

$1^n$

t (n)

$t(n)$

t (m)

$t(m)$

m < n

$m < n$

m < n

$m < n$

t (n) = t (m)

$t(n)=t(m)$

n

$n$

n_{s}

$n_s$

s

$s$

L (1^{n}) = 0

$L(1^n) = 0$

s

$s$

n_{s}

$n_s$

t

$t$

L (1^{n})

$L(1^n)$