¿Existe algún problema conocido de NP-Completo (o NP-Intermedio) en el espacio no lineal subdeterminado?

Hay algunos problemas NP-Complete ( , , etc.) que se sabe que están en . ¿Qué pasa con los espacios sub-lineales? $\mathsf{SAT}$ $\mathsf{SUBSETSUM}$ $\mathsf{DSPACE(n)}$

¿Existe algún problema conocido de NP-Completo (o NP-Intermedio) en el espacio no lineal subdeterminado ?

cc.complexity-theory np-hardness nondeterminism np-intermediate Abuzer Yakaryilmaz
fuente

Respuestas:

La versión plana de muchos problemas NP-completos pertenecen a para algunos $NTISP(n,n^q)$ $q<1$

Véase, por ejemplo, " Límites inferiores y problemas completos en clases de complejidad lineal no lineal y tiempo lineal no lineal " de P. Chapdelaine y E. Grandjean (2006)

Marzio De Biasi
fuente

¡Gracias! ¿Tienes alguna idea sobre el espacio polilogarítmico?

Abuzer Yakaryilmaz

Cualquier problema tiene una versión así, ¡solo PAD! Por ejemplo, el lenguaje que consiste en un verdadero 3CNF de longitud m seguido de m ^ 2 0 está en DSPACE (sqrt (n)).

domotorp
fuente

¡Gracias! ¿Tienes alguna idea sobre el espacio polilogarítmico?

Abuzer Yakaryilmaz

simplemente rellena un 3CNF con

ceros?

2^{\sqrt{n}}

$2^{\sqrt{n}}$

Sasho Nikolov

@ Sasho: Entonces el problema dejaría de ser NP-completo, solo puede PAD con un número polivinílico de ceros.

domotorp

@Abuzer: Creo que el espacio poli-log implicaría que NP es parte de DTIME [

]. Esto es abierto e improbable.

2^{p o l y - l o g}

$2^{poly-log}$

domotorp

@domotorp: ¡Sí, tienes razón! ¡Gracias!

Abuzer Yakaryilmaz

Para cualquier idioma en existe una prueba que se puede verificar utilizando el espacio de trabajo . Uno solo necesita usar las mismas ideas que se usan para probar que SAT es -completo. Por definición, dado un lenguaje , sabemos que existe una máquina Turing tal que para cualquier existe un tal que acepta. Podemos construir una prueba verificable de espacio de registro para escribiendo $\mathsf{NP}$ $O(\log n)$ $\mathsf{NP}$ $\mathsf{NP}$ $L$ $M$ $x \in L$ $y$ $M(x, y)$ $x$ $y$ y el cuadro de cálculo de en la entrada . Es fácil verificar en el cuadro logspace que describe una aceptación de cálculo válida de . Del mismo modo, para cualquier y cualquier , no se acepta ningún cálculo válido de , por lo que el verificador de espacio de registro no aceptará ningún cuadro. $M$ $x, y$ $M$ $x \not \in L$ $y$ $M(x, y)$

Por supuesto, esto no muestra que (porque eso implicaría ). La razón es que el verificador tiene acceso bidireccional a la prueba (puede ir y venir). La definición del verificador de prueba de le da al verificador de espacio de registro solo acceso unidireccional a la prueba (una vez que se lee un poco de la prueba y la cabeza se mueve hacia la derecha, no puede moverse hacia la izquierda). $\mathsf{NP} = \mathsf{NL}$ $\mathsf{NP} = \mathsf{P}$ $\mathsf{NL}$

Sasho Nikolov
fuente

No entiendo la idea! ¿Te refieres a la verificación probabilística? Si es así, en realidad el espacio constante es suficiente para cualquier lenguaje en NP ya que

. ¿O quiere decir la reducción del espacio logarítmico de cualquier idioma en NP a SAT? Estoy realmente confundido!

D S P A C E (2^{n}) \subseteq I P (1)

$DSPACE(2^n) \subseteq IP(1)$

Abuzer Yakaryilmaz

Permítanme intentarlo de otra manera: una forma estándar de definir

es como la clase de lenguajes que tienen verificadores deterministas de polytime. Estoy diciendo que una definición equivalente es definir

como la clase de lenguajes que tienen verificadores deterministas de espacio de registro con acceso de lectura múltiple a la prueba. No se necesita aleatoriedad.

N P

$\mathsf{NP}$

N P

$\mathsf{NP}$

Sasho Nikolov

Gracias. En realidad lo sabía :) La clase no determinista del espacio logarítmico basada en su explicación se denota

, y sí,

. Además,

N S P A C E_{o f f - l i n e} (l o g)

$\mathsf{NSPACE_{off\mbox{-}line}(log)}$

N P = N S P A C E_{o f f - l i n e} (l o g)

$\mathsf{NP} = \mathsf{NSPACE_{off\mbox{-}line}(log)}$

. La noción "fuera de línea" y "en línea", como usted señaló, representan los tipos de acceso a la prueba dada. REF: Sección 5.3.1 de Complejidad computacional de Oded Goldreich (2008).

N L = N S P A C E_{o n - l i n e} (l o g)

$\mathsf{NL} = \mathsf{NSPACE_{on\mbox{-}line}(log)}$

Abuzer Yakaryilmaz