Como podemos expressar "

9
  1. Como podemos expressar " P = P S P A C EP=PSPACE " como uma fórmula de primeira ordem?
  2. Qual nível da hierarquia aritmética contém essa fórmula (e qual é o nível mínimo atualmente conhecido da hierarquia que a contém)?

Para referência, consulte esta postagem no blog de Lipton .

Marte
fonte
11
postado cruzadamente
mars
11
Talvez você possa usar a mesma prova de Lipton usando um problema completo do PSPACE em vez de SAT na definição de ψ ( x , c , y ) e obtém que P P S P A C E pode ser expresso como x , cψ(x,c,y)PPSPACEyψ ( x , c , y ) ou seja, é umasentença de Π 2 . Mas IMO é uma espécie de "hack" ... :-)x,cyψ(x,c,y)Π2
Marzio De Biasi
3
Eu apostaria minha vida e todas as posses mundanas que você pode representá-lo como "Falso". Ou seja, é expressável mesmo na lógica proposicional. :)
Shaull
3
@Shaull. Certo. E depois de mostrar que essa é a representação correta, você poderá comprar todos os bens de que precisa. Por favor, não proteste que o espaço para comentários seja muito curto para conter uma prova.
Vijay D
3
@VijayD - Vou morder a isca: encontrei uma prova verdadeiramente maravilhosa e o espaço para comentários é suficiente. Mas eu não gosto do tipo de letra ...
Shaull

Respostas:

25

Em primeiro lugar, quero abordar os comentários da pergunta, em que foi sugerido que "falso" expressa P = P S P A C E porque a afirmaçãoéfalsa. Embora isso possa ser uma boa piada, é realmente muito prejudicial pensar dessa maneira. Quando perguntamos como expressar uma certa sentença em um determinado sistema formal, não estamos falando sobre valores da verdade. Se estivéssemos, então quando alguém perguntou: "Como escrevo o fato de que existem infinitos primos?" poderíamos responder "3 + 3 = 6", mas isso claramente não funciona. Pelo mesmo motivo, "false" não é uma resposta válida para "P=PSPACEP=PSPACEAcho que Frege e Russell tentaram nos ensinar essa lição. Ok, agora a resposta.

Deixe-me mostrar como expressar P S P A C E P , a outra direção é semelhante e, em seguida, você pode reuni-los em conjunto para obter P S P A CPSPACEP E = P . De qualquer forma, para seus propósitos, pode ser suficiente expressar apenas P S P A C E P , dependendo do que você está fazendo.PSPACE=PPSPACEP

Usando técnicas semelhantes às da construção do predicado TT de Kleene , podemos construir uma fórmula quantificada limitada a c c e p t s p a c e ( k , m , n ) (que assim reside em Σ 0 0 = Π 0 0 ) dizendo "quando executamos a máquina codificada por ke vinculamos seu uso de espaço a | n | m , a máquina aceita a entrada n ." Aqui | n |acceptspace(k,m,n)Σ00=Π00k|n|mn|n| comprimento de n . Uma maneira informal de ver que essas fórmulas existem é esta: dado k , mnkm, e n podemos calcular o limite recursivo primitivo de quanto tempo e quanto espaço vamos precisar (ou seja, no máximo | nn | m espaço e no máximo 2 | n | m de tempo). Simplesmente pesquisamos todos os traços de execução possíveis que estão dentro dos limites computados - essa pesquisa é bastante ineficiente, mas é primitiva recursiva e, portanto, podemos expressá-la como uma fórmula limitada.|n|m2|n|m

Há uma fórmula semelhante um c c e p t t i m e ( k , m , n ) em que o tempo de execução está ligada por | n | m .accepttime(k,m,n)|n|m

Agora considere a fórmula: k , m . k , m . n . a c c e p t s p a c e ( k , m , n ) a c c e p t t i m e ( k , m , n ) . Diz que para cada máquina k

k,m.k,m.n.acceptspace(k,m,n)accepttime(k,m,n).
kque usa no máximo espaço | n | m existe uma máquina k P . Esta fórmula é Π 0 3 .|n|mkque usa na maioria das vezes | n | m 'de modo que as duas máquinas aceitem exatamente os mesmos n ' s. Em outras palavras, a fórmula diz P S P A C E|n|mnPSPACEPΠ03

Podemos melhorar isso se quisermos expressar, em vez disso, a frase " T Q B F está no polytime", que deve ser boa o suficiente para a maioria das aplicações, pois o TQBF é o PSPACE completo e, portanto, estar no polytime é equivalente a P S P A C E P . Seja k 0 (o código de) uma máquina que reconheça TQBF no espaço | n | m 0 . Em seguida, " T Q B F P " pode ser expressa como k ' , m ' .TQBFPSPACEPk0|n|m0TQBFPn . um c c e p t s p um ce ( k 0 , m 0 ,n)accep t t i m e ( k , m ,n). Esta fórmula é apenas Σ 0 2 . Se eu fosse um teórico da complexidade, saberia se é possível melhorar ainda mais (mas duvido).

k,m.n.acceptspace(k0,m0,n)accepttime(k,m,n).
Σ02
Andrej Bauer
fonte
seu primeiro parágrafo é quase como uma forma lógica e textual disso: xkcd.com/169
Vijay D
21

Andrej já explicou que P = P S P A C E pode ser escrito como uma sentença Σ 0 2 . Deixe-me mencionar que essa classificação é ótima no sentido de que, se a afirmação é equivalente a uma sentença de Π 0 2 , esse fato não é relativizado. Mais precisamente, o conjunto de oráculos A tal que P A = P S P A C E A é definível por uma fórmula Σ 0 2 com uma variável livre de segunda ordem AP=PSPACEΣ02Π02APA=PSPACEAΣ02A, mas não é definível por nenhuma Π 0 2 0 2 - completo no sentido apropriado.)Π02-Fórmula. O argumento é descrito (para P = N P , mas funciona da mesma forma para P S P A C E ) nos comentários em /mathpro/57348 . (De fato, pode-se mostrar por uma elaboração da ideia que o conjunto é ΣP=NPPSPACEΣ02

EDIT: A prova topológica fornecida no comentário vinculado é curta, mas pode parecer complicada. Aqui está um argumento de força direta.

P AP S P A C E A pode ser escrita como umafórmula Π 0 2 da formaPAPSPACEAΠ02 ϕ ( A ) = xyθ ( A , x , y ) , em que θ é Δ 0 0 . Suponha por contradição que P A = P S P A C E A também seja equivalente a umafórmula Π 0 2 ψϕ(A)=xyθ(A,x,y)θΔ00PA=PSPACEAΠ02 ( A ) = xzη ( A , x , z ) . Fixar os oráculos B , C de modo que P BP S P A C E B e P C = P S P A Cψ(A)=xzη(A,x,z)BCPBPSPACEB E C .PC=PSPACEC

Desde ϕ ( B ) , existe y 0 tal que θ ( B , 0 , y 0 ) . No entanto, θ é uma fórmula delimitada, portanto, a avaliação do valor de verdade de θ ( B , 0 , y 0 ) usa apenas uma parte finita do oráculo. Assim, existe uma parte finita b 0 de B tal que θ ( A , 0 , y 0 ) para todo oráculoϕ(B)y0θ(B,0,y0)θθ(B,0,y0)b0Bθ(A,0,y0)A estendendo b 0 .Ab0

Deixe C [ b 0 ] denotar o oráculo que se estende b 0 e concorda com C onde b 0 é indefinido. Como P A e P S P A C E A não são afetados por uma mudança finita no oráculo, temos ψ ( C [ b 0 ] ) . Pelo mesmo argumento acima, existe z 0 e uma parte finita c 0 de C [deC[b0]b0Cb0PAPSPACEAψ(C[b0])z0c0 b 0 ]C[b0]tal que η ( A , 0 , z 0 ) para cada A que se estende c 0 . Podemos assumir que c 0 estende b 0 .

Continuando da mesma maneira, construímos sequências infinitas de números y 0 , y 1 , y 2 , , z 0 , z 1 , z 2 , e oráculos parciais finitos b 0c 0b 1c 1b 2 tal que

  1. θ ( A , n , y n ) para cada oráculo A que se estende b n ,

  2. η ( A , n , z n ) para todo oráculo A que se estende c n .

Agora, seja A um oráculo que estende todos os b n e c n . Então 1 e 2 implicam que ϕ ( A ) e ψ ( A ) são válidos simultaneamente, o que contradiz a suposição de que eles são complementos um do outro.

Emil Jeřábek
fonte
3
Sad that such a nice answer is for a question that's now closed...
arnab