Teoría de la complejidad estructural
Sabemos que L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} y que L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , donde L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . También sabemos que...
Muchos resultados importantes en la teoría de la complejidad computacional, y en particular la teoría de la complejidad "estructural", tienen la propiedad interesante de que pueden entenderse como fundamentalmente siguientes (como lo veo ...) de los resultados algorítmicos que proporcionan un...
Rompecabezas Dado que el problema es largo aquí hay un caso especial que captura su sentido. Problema: Sea A un algoritmo detrminístico para 3-SAT. Es el problema de simular completamente el algoritmo A (en cada instancia del problema). P-Space duro? (Más precisamente, ¿hay razones para creer...
Antecedentes Se sabe que existe un oráculo AAA tal que, P S P A C E A ≠ P H APSPACEA≠PHAPSPACE^A \neq PH^A . Incluso se sabe que la separación es relativa a un oráculo aleatorio. Informalmente, uno puede interpretar que esto significa que hay muchos oráculos para los cuales P S P A C...
No se sabe si isomorfismo gráfico (GI) para gráficos fuertemente regulares (SRGS) está en P . ¿Hay alguna pista de que podría o no ser GI -Complete? ¿Hay alguna consecuencia fuerte en tales casos? (Similar a la creencia de que GI puede no ser
En nuestro trabajo reciente, resolvemos un problema computacional que surgió en un contexto combinatorio, suponiendo que , donde es el -versión de . El único artículo sobre que encontramos fue el artículo de Beigel-Buhrman-Fortnow 1998 que se cita en Complexity Zoo . Entendemos que podemos tomar...
Dos documentos que incluiría son: D. Kozen, "Indización de clases subrecursivas" , STOC, 1978. R. Ladner, "Sobre la estructura de la reducibilidad del tiempo polinomial" , JACM,
Para cualquier lenguaje NP arbitrario completo, ¿hay siempre un superconjunto polytime cuyo complemento también es infinito? Se ha pedido una versión trivial que no estipula que el superconjunto tenga un complemento infinito en /cs//q/50123/42961 A los fines de esta pregunta, puede suponer que ....
¿ implica E = N E ?E XP = N E X PEXP=NEXP\mathsf{EXP}=\mathsf{NEXP}E = N
Sea la clase de lenguajes que se decida alternando máquinas de Turing que se detengan en el tiempo utilizando el espacio . Sea la clase de lenguajes que se decida alternando máquinas de Turing que dejen de usar las alternancias y el espacio .f ( n ) g ( n ) A A L T S P ( f ( n ) , g ( n ) ) f ( n )...
La conjetura del isomorfismo de Berman y Hartmanis establece que todos los conjuntos completos de son polinomiales en el tiempo isomorfos entre sí. Esto significa que los completos de pueden reducirse eficazmente entre sí mediante bijecciones de tiempo polinómico computables e invertibles. La...