- Como podemos expressar " P = P S P A C E
P=PSPACE " como uma fórmula de primeira ordem? - 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 .
Respostas:
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=PSPACE P=PSPACE Acho 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 CPSPACE⊆P 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=P PSPACE⊆P
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=Π00 k |n|m n |n| comprimento de n . Uma maneira informal de ver que essas fórmulas existem é esta: dado k , mn k m , 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|m 2|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
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 ' .TQBF PSPACE⊆P k0 |n|m0 TQBF∈P ∀ n . 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).
fonte
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 Π02 A PA=PSPACEA Σ02 A , 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=NP PSPACE Σ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 A ≠ P S P A C E A pode ser escrita como umafórmula Π 0 2 da formaPA≠PSPACEA Π02 ϕ ( A ) = ∀ x∃ yθ ( 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)=∀x∃yθ(A,x,y) θ Δ00 PA=PSPACEA Π02 ( A ) = ∀ x∃ zη ( A , x , z ) . Fixar os oráculos B , C de modo que P B ≠ P S P A C E B e P C = P S P A Cψ(A)=∀x∃zη(A,x,z) B C PB≠PSPACEB 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) b0 B θ(A,0,y0) A estendendo b 0 .A b0
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] b0 C b0 PA PSPACEA ψ(C[b0]) z0 c0 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 0 ⊆ c 0 ⊆ b 1 ⊆ c 1 ⊆ b 2 ⊆ ⋯ tal que
θ ( A , n , y n ) para cada oráculo A que se estende b n ,
η ( 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.
fonte