¿Existe algún lenguaje completo en el espacio(n)?

Question

¿Tiene el espacio(n) un lenguaje completo? En realidad lo siguiente estaba en un examen final del curso de complejidad :

si A es SPACE(n) difícil entonces A es también PSPACE difícil

(se supone que esto se muestra por el relleno... no sé cómo exactamente)

creo que es falso (si space(n) tiene un lenguaje completo entonces es trivialmente falso) debido a la prueba de que TBQF es PSPACE-completo (con algunas modificaciones menores, creo que se puede demostrar que hay un lenguaje que es space(n) hard (no nessesarily completo) que se decide por un O(n^k) para algún valor pequeño de k). ¡Pero no estoy seguro!

Answer 1

El truco del relleno para demostrar que si $A$ es DSPACE( $n$ )-duro entonces es también PSPACE-duro es bastante estándar y va como sigue. Comience con un lenguaje arbitrario $B$ en PSPACE, digamos en DSPACE( $n^k$ ). Sea $B'$ ser la versión "acolchada" de $B$ definido como el conjunto de palabras de la forma $$ x01^{|x|^k} $$ para $x \in B$ . Tenga en cuenta que $B'$ está en DSPACE( $n$ ) ya que se nos da el espacio para simular el $n^k$ -en la entrada, y que hay una reducción trivial de $B$ a $B'$ : $$ x \mapsto x01^{|x|^k}. $$ Ahora bien, como $A$ es DSPACE( $n$ )-duro y $B'$ está en DSPACE( $n$ ), también existe una reducción en tiempo polinómico de $B'$ a $A$ . Componiendo las reducciones obtenemos la de $B$ a $A$ .

Nótese que este hecho no es incompatible con DSPACE( $n$ ) que tiene un lenguaje completo (bajo reducciones de tiempo polinómico) y el hecho de que DSPACE( $n$ ) $\not=$ PSPACE porque DSPACE( $n$ ) no está cerrado bajo reducciones de tiempo polinómico. Si DSPACE( $n$ ) tiene realmente un lenguaje completo es una historia diferente. Los candidatos estándar (QBF, máquina universal de espacio limitado, etc.) incurren $O(\log n)$ en las codificaciones para tener en cuenta los alfabetos ilimitados o el número ilimitado de cintas en las máquinas que definen DSPACE( $n$ ), por lo que no funcionan directamente. Un trabajo relativamente reciente de Ryan Williams en el que examina la eficiencia de las codificaciones podría ser relevante para esto (ver http://www.cs.cmu.edu/~ryanw/qbf-lower-bd.pdf ).

Answer 2

¡¡¡Gracias!!! ¡¡¡¡La explicación del acolchado ha sido muy ilustrativa!!!!

También entiendo que la parte de que DSPACE(n) tenga un lenguaje completo no contradice lo anterior, pero incluso si hay un lenguaje duro O(n^{3}) DSPACE(n) (a eso me refería cuando mencionaba un lenguaje O(n^{k}) para alguna k pequeña) entonces esto podría llevar a una contradicción (depende del tamaño de la reducción...ya que un lenguaje O(n^k) (k>>3) podría reducirse a este lenguaje DSPACE(n)-duro pero la reducción podría dar lugar a una entrada de tamaño O(n^{k/3}) para la máquina que decide este lenguaje DSPACE(n)-duro)...pero si este no es el caso esto podría llevar a SPACE(n^{k_{1}}) = SPACE(n^{k_{2}}), con k_{1} < k_{2}.

¡¡¡gracias de nuevo!!!

Answer 3

Un lenguaje completo canónico para $LINSPACE = DSPACE(n)$ sería la siguiente redacción

$L =\{ < M,x,1^s>\ :\ M\ \text{is a Turing machine that accepts}\ x\ \text{using space}\ s\}$

que está completo para $LINSPACE$ bajo reducciones de tiempo lineal, reducciones de espacio logarítmico, así como reducciones de tiempo polinómico.

Aquí las reducciones de tiempo lineal son posiblemente las reducciones más naturales, ya que LINSPACE está cerrado bajo reducciones de tiempo lineal estas. En cuanto a las reducciones de tiempo logspace y polinomial, el lenguaje $L$ arriba es incluso difícil para $PSPACE$ bajo estas reducciones.

Otra cosa que hay que mencionar sobre el espacio lineal es la conexión con lenguas sensibles al contexto . Las máquinas de Turing que operan en el espacio lineal también se conocen como autómatas lineales acotados. Mediante las gramáticas se pueden definir lenguajes completos (algo más naturales) para $LINSPACE$ y $NLINSPACE=NSPACE(n)$ que los problemas completos canónicos.

Answer 4

Si consideramos sólo las reducciones log-espaciales, ¿puede ser entonces que L (arriba) sea también PSPACE-difícil? (¿el truco del relleno no sugiere que usemos la reducción polinomial-espacial?)