¿Cómo podemos expresar "

¿Cómo podemos expresar " " como una fórmula de primer orden? $P=PSPACE$
¿Qué nivel de la jerarquía aritmética contiene esta fórmula (y cuál es el nivel mínimo actualmente conocido de la jerarquía que la contiene)?

Como referencia, vea esta publicación de blog de Lipton .

cc.complexity-theory lo.logic descriptive-complexity Marte
fuente

publicado en forma cruzada

marzo

Quizás, puede usar la misma prueba de Lipton usando un problema PSPACE-complete en lugar de SAT en la definición de y obtiene que puede expresarse como es decir, es una oración . Pero en mi opinión es una especie de "pirateo" ... :-)

ψ (x, c, y)

$\psi(x,c,y)$

P \neq P S P A C E

$P \neq PSPACE$

\forall x, c \exists y ψ (x, c, y)

$\forall x,c \; \exists y \; \psi(x,c,y)$

Π_{2}

$\Pi_2$

Marzio De Biasi

Apostaría mi vida y todas las posesiones mundanas a que puedes representarlo como "Falso". Es decir, es expresable incluso en lógica proposicional. :)

Shaull

@Shaull. Por supuesto. Y una vez que demuestre que esta es la representación correcta, podrá comprar todas las posesiones que necesita. No protestes porque el espacio para comentarios es demasiado corto para contener una prueba.

Vijay D

@VijayD - Voy a morder el anzuelo: he encontrado una prueba realmente maravillosa, y el espacio para comentarios es suficiente. Pero no me gusta la fuente ...

Shaull

Respuestas:

En primer lugar, quiero dirigir los comentarios a la pregunta, donde se sugirió que "falso" expresa porque la declaración es falsa. Si bien esto podría ser una buena broma, en realidad es muy perjudicial pensar de esta manera. Cuando preguntamos cómo expresar una determinada oración en un determinado sistema formal, no estamos hablando de valores de verdad. Si lo fuéramos, entonces cuando alguien preguntó "¿Cómo escribo el hecho de que hay infinitos números primos?" podríamos responder "3 + 3 = 6", pero esto claramente no servirá. Por la misma razón, "falso" no es una respuesta válida a "¿cómo escribo ?". Creo que Frege y Russell se esforzaron por enseñarnos esa lección. Ok, ahora a la respuesta. $P = PSPACE$ $P = PSPACE$

Te voy a enseñar cómo expresar , la otra dirección es similar, y luego se puede ponerlos juntos en una conjunción de conseguir . En cualquier caso, para sus propósitos puede ser suficiente expresar solo , dependiendo de lo que esté haciendo. $PSPACE \subseteq P$ $PSPACE = P$ $PSPACE \subseteq P$

Usando técnicas similares a las de la construcción del predicado $T$ de Kleene , podemos construir una fórmula de limitada accept_ (que por lo tanto reside en ) que dice "cuando ejecute la máquina codificada por y limite su uso de espacio a , la máquina acepta la entrada ". Aquíes la longitud de . Una manera informal de ver que tales fórmulas que existe es la siguiente: dado , y se puede calcular recursiva primitiva con destino en la cantidad de tiempo y la cantidad de espacio que alguna vez va a necesitar (es decir, a lo sumo $accept_{space}(k, m, n)$ $\Sigma^0_0 = \Pi^0_0$ $k$ $|n|^m$ $n$ $|n|$ $n$ $k$ $m$ $n$ $|n|^m$ espacio y como máximo tiempo). Luego, simplemente buscamos a través de todos los rastros de ejecución posibles que se encuentran dentro de los límites calculados; dicha búsqueda es bastante ineficiente, pero es primitiva recursiva y, por lo tanto, podemos expresarla como una fórmula acotada. $2^{|n|^m}$

Hay una fórmula similar en la que el tiempo de ejecución está limitado por . $accept_{time}(k, m, n)$ $|n|^m$

Ahora considere la fórmula: Dice que para cada máquina que usa en la mayoría del espacio hay una máquina que usa en la mayoría del tiempo modo que las dos máquinas acepten exactamente las mismas 's. En otras palabras, la fórmula dice . Esta fórmula es .

\forall k, m . \exists k^{'}, m^{'} . \forall n . a c c e p t_{s p a c e} (k, m, n) \Leftrightarrow a c c e p t_{t i m e} (k^{'}, m^{'}, n) .

$\forall k, m . \exists k', m' . \forall n . accept_{space}(k,m,n) \Leftrightarrow accept_{time}(k',m', n).$

k

$k$

| n |^{m}

$|n|^m$

k^{'}

$k'$

| n |^{m^{'}}

$|n|^{m'}$

n

$n$

P S P A C E \subseteq P

$PSPACE \subseteq P$

Π_{3}^{0}

$\Pi^0_3$

Podemos mejorar esto si estamos dispuestos a expresar en cambio la frase " está en polytime", que debe ser lo suficientemente bueno para la mayoría de aplicaciones, como TQBF es PSPACE completa y por lo tanto estar en polytime es equivalente a . Deje ser (el código de) una máquina que reconoce TQBF en el espacio . Entonces " " puede expresarse como Esta fórmula es solo . Si fuera un teórico de la complejidad, sabría si es posible hacerlo aún mejor (pero lo dudo). $TQBF$ $PSPACE \subseteq P$ $k_0$ $|n|^{m_0}$ $TQBF \in P$

\exists k^{'}, m^{'} . \forall n . a c c e p t_{s p a c e} (k_{0}, m_{0}, n) \Leftrightarrow a c c e p t_{t i m e} (k^{'}, m^{'}, n) .

$\exists k', m' . \forall n . accept_{space}(k_0, m_0, n) \Leftrightarrow accept_{time}(k', m', n).$

Σ_{2}^{0}

$\Sigma^0_2$

Andrej Bauer
fuente

su primer párrafo es casi como una forma lógica y textual de esto: xkcd.com/169

Vijay D

Andrej ya ha explicado que puede escribirse como una 0_2. Permítanme mencionar que esta clasificación es óptima en el sentido de que si la declaración es equivalente a una 0_2, entonces este hecho no se relativiza. Más precisamente, el conjunto de oráculos tal que es definible por una 0_2 con una variable libre de segundo orden , pero no es definible por ninguna fórmula. El argumento se describe (para , pero funciona igual para ) en los comentarios en $P=\mathit{PSPACE}$ $\Sigma^0_2$ $\Pi^0_2$ $A$ $P^A=\mathit{PSPACE}^A$ $\Sigma^0_2$ $A$ $\Pi^0_2$ $P=\mathit{NP}$ $\mathit{PSPACE}$ /mathpro/57348 . (De hecho, uno puede demostrar mediante una elaboración de la idea que el conjunto es -completo en el sentido apropiado). $\Sigma^0_2$

EDITAR: La prueba topológica dada en el comentario vinculado es corta, pero puede parecer complicada. Aquí hay un argumento de forzamiento directo.

$P^A\ne\mathit{PSPACE}^A$ se puede escribir como una de la forma , donde es . Suponga por contradicción que también es equivalente a a -formula . Oráculos Fix , de tal manera que y . $\Pi^0_2$ $\phi(A)=\forall x\,\exists y\,\theta(A,x,y)$ $\theta$ $\Delta^0_0$ $P^A=\mathit{PSPACE}^A$ $\Pi^0_2$ $\psi(A)=\forall x\,\exists z\,\eta(A,x,z)$ $B$ $C$ $P^B\ne\mathit{PSPACE}^B$ $P^C=\mathit{PSPACE}^C$

Desde , existe tal que . Sin embargo, es una fórmula acotada, por lo tanto, la evaluación del valor de verdad de solo usa una parte finita del oráculo. Por lo tanto, existe una parte finita de tal que para cada oráculo extiende . $\phi(B)$ $y_0$ $\theta(B,0,y_0)$ $\theta$ $\theta(B,0,y_0)$ $b_0$ $B$ $\theta(A,0,y_0)$ $A$ $b_0$

Supongamos que denota el oráculo que extiende y está de acuerdo con donde no está definido. Como y no se ven afectadas por un cambio finito en el oráculo, tenemos . Por el mismo argumento anterior, existe y una parte finita de tal que para cada extiende . Podemos suponer que extiende . $C[b_0]$ $b_0$ $C$ $b_0$ $P^A$ $\mathit{PSPACE}^A$ $\psi(C[b_0])$ $z_0$ $c_0$ $C[b_0]$ $\eta(A,0,z_0)$ $A$ $c_0$ $c_0$ $b_0$

Continuando de la misma manera, construimos secuencias infinitas de números , y oráculos parciales finitos tales que $y_0,y_1,y_2,\dots$ $z_0,z_1,z_2,\dots$ $b_0\subseteq c_0\subseteq b_1\subseteq c_1\subseteq b_2\subseteq\cdots$

$\theta(A,n,y_n)$ para cada oráculo extiende , $A$ $b_n$
$\eta(A,n,z_n)$ para cada oráculo extiende . $A$ $c_n$

Ahora, dejemos que sea un oráculo que extienda todo y . Entonces 1 y 2 implican que y se mantienen simultáneamente, lo que contradice la suposición de que son complementos entre sí. $A$ $b_n$ $c_n$ $\phi(A)$ $\psi(A)$

Emil Jeřábek
fuente

Es triste que una respuesta tan agradable sea para una pregunta que ahora está cerrada ...

arnab