¿Cuáles son las consecuencias de

46

Sabemos que LNLP y que LNLL2 polyL , donde L2=DSPACE(log2n) . También sabemos que polyLPporque el último tiene problemas completos bajo el espacio logarítmico reducciones de muchos uno mientras que el primero no (debido al teorema de la jerarquía del espacio). Con el fin de comprender la relación entre polyL y P , que puede ayudar a entender primero la relación entre L2 y P .

¿Cuáles son las consecuencias de L2P ?

¿Qué pasa con el más fuerte LkP para k>2 , o el más débil L1+ϵP para ϵ>0 ?

argentpepper
fuente
44
@OrMeir Recientemente agregué una explicación de este hecho al artículo de Wikipedia para polyL .
argentpepper
13
L2PLPLL2
12
Buena pregunta! Creo que definitivamente vale la pena una recompensa. Por cierto, aquí hay una observación simple, si , entonces . Por lo tanto, tenemos un algoritmo más eficiente para CNF-SAT y rechazamos ETH (hipótesis de tiempo exponencial). L2PDSPACE(n)DTIME(2O(n))
Michael Wehar
3
Siguiendo el comentario de @ MichaelWehar, la implicación se deriva de un argumento de relleno estándar que se extiende a hipótesis más débiles: si L1+ϵ está en P , entonces cualquier problema que pueda resolverse en un espacio lineal (incluido el problema de satisfacción), puede se resolverá a tiempo 2O(n11+ϵ) .
argentpepper
3
@SajinKoroth: Creo que su comentario, así como el de Michael Wehar (y el seguimiento de argentpepper) deberían ser respuestas ...
Joshua Grochow

Respuestas:

26

La siguiente es una consecuencia obvia: implicaría y, por lo tanto, .L P L PL1+ϵPLPLP

Según el teorema de la jerarquía espacial, . Si entonces .L 1 + ϵP LL 1 + ϵPϵ>0:LL1+ϵL1+ϵPLL1+ϵP

Sajin Koroth
fuente
Pequeña nota al pie: Si , entonces tenemos o . P N L N L LPLPNLNLL
Michael Wehar
27

L2P refutaría la hipótesis del tiempo exponencial .

Si entonces mediante un argumento de relleno . Esto significa que el problema de satisfacción se puede decidir en pasos, refutando la hipótesis del tiempo exponencial.L2P DSPACE(n)DTIME(2O(n))SATDSPACE(n)2o(n)

Más generalmente, para implica .DSPACE(logkn)Pk1SATDSPACE(n)DTIME(2O(n1k))

(Esta respuesta se expande a partir de un comentario de @MichaelWehar).

argentpepper
fuente
¡Gracias por ampliar el comentario! Lo aprecio. :)
Michael Wehar
1
Además, la última hipótesis también implica que está en DSPACE ( ) DTIME ( ). QBFn2O(n1k)
Michael Wehar
8

El isomorfismo grupal (con grupos dados como tablas de multiplicación) estaría en P. Lipton, Snyder y Zalcstein mostraron que este problema está en , pero aún está abierto si está en P. El mejor límite superior actual es tiempo, y debido a que se reduce al isomorfismo gráfico, se erige como un obstáculo significativo para poner la iso del gráfico en P.L2nO(logn)

Me hace preguntarme a qué otros problemas naturales e importantes se aplicaría esto: es decir, en pero con su cuasi-polinomio de límite superior de tiempo más conocido.L2

Joshua Grochow
fuente
1
Más específicamente, el problema más general del isomorfismo de cuasigrupo está en , que es una subclase de . β2FOLLL2
argentpepper el
1
Además, el problema de rango de grupo (dado un grupo finito G como tabla de multiplicación y un entero k , ¿ G tiene un conjunto generador de cardinalidad k ?) También tiene esta propiedad. El algoritmo es solo una búsqueda en los subconjuntos de G de la cardinalidad k pero utiliza dos hechos importantes: (1) cada grupo finito tiene un conjunto generador de tamaño logarítmico y (2) la pertenencia a un subgrupo está en , que es igual a . SLL
argentpepper el
1

Reclamación: si para algunos , entonces y .LkPk>2Plog(CFL)PNL

Supongamos que para algunos .LkPk>2

Desde " Límites de memoria para el reconocimiento de lenguajes sin contexto y sensibles al contexto ", sabemos que . Por el teorema de la jerarquía espacial, sabemos que .CFLDSPACE(log2(n))DSPACE(log2(n))DSPACE(logk(n))

Por lo tanto, obtenemos .log(CFL)DSPACE(log2(n))DSPACE(logk(n))P

Además, según el Teorema de Savitch, sabemos que . Por lo tanto, obtenemos .NLL2NLDSPACE(log2(n))DSPACE(logk(n))P

Michael Wehar
fuente