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

9

Hay algunos problemas NP-Complete ( , , etc.) que se sabe que están en . ¿Qué pasa con los espacios sub-lineales?SUNATD S P A C E ( n )SUsiSmiTSUMETROreSPAGSUNACmi(norte)

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

Abuzer Yakaryilmaz
fuente

Respuestas:

14

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
1
simplemente rellena un 3CNF con ceros? 2norte
Sasho Nikolov
2
@ Sasho: Entonces el problema dejaría de ser NP-completo, solo puede PAD con un número polivinílico de ceros.
domotorp
1
@Abuzer: Creo que el espacio poli-log implicaría que NP es parte de DTIME [ ]. Esto es abierto e improbable. 2pagsoly-losol
domotorp
@domotorp: ¡Sí, tienes razón! ¡Gracias!
Abuzer Yakaryilmaz
11

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

Por supuesto, esto no muestra que (porque eso implicaría N P = P ). 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 N L 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).nortePAGS=norteLnortePAGS=PAGSnorteL

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! reSPAGSUNACmi(2norte)yoPAGS(1)
Abuzer Yakaryilmaz
1
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 N P 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. nortePAGSnortePAGS
Sasho Nikolov
44
Gracias. En realidad lo sabía :) La clase no determinista del espacio logarítmico basada en su explicación se denota , y sí, N P = N S P A C E o f f - l i n e ( l o g ) . Además, N L = N S P A CnorteSPAGSUNACmioFF-lyonortemi(losol)nortePAGS=norteSPAGSUNACmioFF-lyonortemi(losol) . 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). norteL=norteSPAGSUNACmionorte-lyonortemi(losol)
Abuzer Yakaryilmaz