¿Cuáles son las razones de peso para creer

23

¿Cuáles son las razones de peso para creer ? L es la clase de algoritmos de espacio logarítmico con punteros a la entrada. $L\neq P$

Supongamos que L = P por el momento. ¿Cómo sería un algoritmo de espacio logarítmico para un problema P-completo en sus esquemas generales?

cc.complexity-theory complexity-classes Jumer
fuente

2

en cierto sentido, sería un algoritmo de compresión de espacio para un cómputo de máquina de Turing en tiempo P que generalmente ocupa espacio en P. por lo tanto, si L ≠ P, entonces hay algún "límite de compresibilidad (in)" de P. una posible dirección de construcción / pregunta / investigación basada en este ángulo, compresión de la secuencia de ejecución TM

vzn

1

vea también la separación de la publicación de blog de L / P & kintalis citada allí

vzn

28

El resultado de Mulmuley (de la página web de Mulmuley sin paywall) que, en el modelo PRAM sin operaciones de bit, " ". (En el modelo booleano habitual donde vive , .) Este modelo es lo suficientemente fuerte como para que el resultado implique cualquier algoritmo para a -complete problema tendría que verse bastante diferente de la mayoría de los algoritmos conocidos para -complete problemas. $\mathsf{P} \neq \mathsf{NC}$ $\mathsf{L}$ $\mathsf{L} \subseteq \mathsf{NC}$ $\mathsf{L}$ $\mathsf{P}$ $\mathsf{P}$

El modelo PRAM sin operaciones de bits es un modelo algebraico no uniforme sobre (similar a los árboles de cómputo algebraico o al modelo de RAM algebraico Blum - Shub - Smale) en el que el programa no uniforme puede depender no solo del número de entradas enteras, pero también en su longitud de bit total. De esta manera no es un modelo algebraico "puramente", sino que vive en algún lugar entre algebraico y booleano. Este modelo incluye algoritmos de poli-tiempo para programación lineal, maxflow, mincut, árbol de expansión ponderado, rutas más cortas y otros problemas de optimización combinatoria, el algoritmo de espacio de registro para isomorfismo de árbol (ver comentarios a continuación) y algoritmos para aproximar las raíces complejas de polinomios, por eso digo cualquier algoritmo para a $\mathbb{Z}$ $\mathsf{L}$ $\mathsf{P}$ -completo problema (que, como su pregunta indica que sabe, la mayoría de la gente piensa que no existe) tendría que verse muy diferente de cualquiera de estos.

Joshua Grochow
fuente

En su conjetura en la página 62, ¿cómo relaciona Mulmuley

con mincost-flow? ¿Por qué

tiene que ser lineal y

una biyección? La conjetura parece implicar que ningún mapa lineal de rango

(dado que el mapa inverso de un mapa lineal 1−1 es lineal) evaluado en un conjunto cero de

puede cubrir

. ¿Es correcta mi interpretación?

S L_{m} (C)

$SL_m(C)$

L

$L$

F

$F$

k

$k$

S L_{m} (C)

$SL_m(C)$

L (n)

$L(n)$

T ....

φ

$\varphi$

φ (x) = det (F (x))

$\varphi(x) = \det(F(x))$

x \in L (n)

$x \in L(n)$

det (F (x)) = 1

$\det(F(x)) = 1$

x \in F^{- 1} (S L_{m})

$x \in F^{-1}(SL_m)$

la única suposición es que parece ser el caso. ¡Bastante interesante! Al igual que con otras suposiciones y pruebas de complejidad: ¿se conoce la otra manera: es decir, si , es ? Nunca he visto tales conversaciones en la teoría de la complejidad o ¿tales conversaciones no son posibles?

d e t \notin N C^{1}

$det\notin NC^{1}$

d e t \in N C^{1}

$det\in NC^1$

P = N C

$P=NC$

T ....

@JAS: No veo a qué te refieres con "la única suposición es ...": no creo que se deduzca que , si eso es lo que estabas diciendo ...

det \notin N C^{1} \Rightarrow P \neq N C

$\det \notin NC^1 \Rightarrow P \neq NC$

Joshua Grochow

1

@JAS: La creencia de que apoya la conjetura, pero no implica la conjetura. Menciona lo contrario, que si la coincidencia perfecta entonces la conjetura es falsa para la pequeña . De manera equivalente, si la conjetura es verdadera, entonces la coincidencia perfecta . Tenga en cuenta que esta es la dirección opuesta a lo que estaba diciendo.

d e t \notin N C^{1}

$det \notin NC^1$

\in N C^{1}

$\in NC^1$

a

$a$

\notin N C^{1}

$\notin NC^1$

Joshua Grochow

15

Hay una serie de trabajos de M. Hofmann y U. Schöpp que formaliza la noción intuitiva de "algoritmos espaciales logarítmicos típicos", utilizando solo un número constante de punteros a la estructura de datos de entrada, como un lenguaje de programación PURPLE (programas de puntero puro con iteración.)

Aunque los programas PURPLE no capturan todos (se ha demostrado que no pueden decidir la conectividad st no dirigida), se muestra que su extensión con conteo captura una gran fracción de , pero no El problema P-completo Horn-SAT. Esto se muestra en el último artículo de la serie: M. Hofmann, R. Ramyaa y U. Schöpp: Pure Pointer Programs and Tree Isomorphism, FOSSACS 2013. $\mathsf{L}$ $\mathsf{L}$

La conclusión parece ser que los algoritmos de espacio logarítmico para problemas completos deben ser muy atípicos e ir más allá de lo que se puede implementar en PURPLE con el conteo. $\mathsf{P}$

Jan Johannsen
fuente

55

PÚRPURA con el conteo es un modelo interesante y corresponde a mi ingenua intuición de algoritmos de espacio de registro. Pero no sé si este resultado es una buena evidencia de : incluso dicen "Entonces, la satisfacción de Horn no puede decidirse en PURPLE aumentada con no determinismo y contando tampoco, sino por la misma razón que un problema de LOGSPACE en particular, a saber el isomorfismo de los árboles no puede ". Esto esencialmente dice que el resultado es realmente sobre la debilidad del recuento PÚRPURA + (correspondiente a la intuición ingenua de los algos del espacio de registro) en lugar de la debilidad de L ...

L \neq P

$L \neq P$

Joshua Grochow

3

La complejidad descriptiva ha intentado proporcionar algunas respuestas.

FO (lógica de primer orden), con ord (ordenamiento del dominio) y TC (cierre transitivo) . $= L$

FO + ord + LFP (punto menos fijo) . $= P$

Entonces surge la pregunta: ¿FO + ord + TC FO + ord + LFP? $\subset$

Por otro lado, ¡FO + LFP (sin ord) ni siquiera puede contar! Por ejemplo, no puede expresar el hecho de que la cardinalidad del dominio es par. Esta lógica ciertamente no puede capturar , pero la pregunta es, ¿puede capturar o ? $P$ $L$ $NL$

Ver por ejemplo http://www.cs.umass.edu/%7Eimmerman/pub/EATCScolumn.pdf

Y luego, la lógica de segundo orden (SO) + Horn captura P, mientras que SO + Krom captura NL. Ver Erich Gradel, Capturando clases de complejidad por fragmentos de lógica de segundo orden , Theoretical Computer Science, 1992.

Martin Seymour
fuente

3

FO + LFP sin ordenar seguramente no puede capturar , por la misma razón que usted cita: no puede contar, ni siquiera el módulo 2.

L

$\mathsf{L}$

Jan Johannsen

De acuerdo. Entonces la pregunta (o más bien, una de las preguntas) es: ¿Es FO + LFP (sin ord) un subconjunto estricto de FO + LFP (con ord)?

Martin Seymour

0

Esto no es realmente una respuesta, pero como se describe aquí , creo que para el -complete problem $\sf{P}$ $\sf{GEN}$ $k$ $\Theta(k \log n)$

NisaiVloot
fuente

¿Cuáles son las razones de peso para creer

Respuestas: