¿Por qué consideramos el espacio logarítmico como un modelo de computación eficiente (en lugar del espacio poligráfico)?

49

Esta podría ser una pregunta subjetiva en lugar de una con una respuesta concreta, pero de todos modos.

En teoría de la complejidad estudiamos la noción de cálculos eficientes. Hay clases como representa el tiempo polinómico y representa el espacio de registro . Se considera que ambos están representados como una especie de "eficiencia" y captan bastante bien las dificultades de algunos problemas.PL

Pero hay una diferencia entre y : mientras que el tiempo polinomial, , se define como la unión de problemas que se ejecuta en el tiempo para cualquier constante , es decir,PLPO(nk)k

P=k0TIME[nk] ,

el espacio de registro, , se define como . Si imitamos la definición de , se convierte enLSPACE[logn]P

PolyL=k0SPACE[logkn] ,

donde se llama la clase de espacio polylog . Mi pregunta es:PolyL

¿Por qué usamos el espacio logarítmico como la noción de computación eficiente, en lugar del espacio polilógico?

Un problema principal puede ser sobre el conjunto completo de problemas. Bajo el espacio de registro de muchas reducciones, tanto como tienen problemas completos. Por el contrario, si tiene problemas completos bajo tales reducciones, entonces habríamos contradicho el teorema de la jerarquía espacial. Pero, ¿qué pasa si pasamos a las reducciones polylog? ¿Podemos evitar tales problemas? En general, si hacemos nuestro mejor para adaptar a la noción de eficiencia y (si es necesario) modificamos algunas de las definiciones para obtener todas las buenas propiedades que debe tener una clase "agradable", ¿hasta dónde podemos llegar?PLPolyLPolyL

¿Hay alguna razón teórica y / o práctica para usar el espacio de registro en lugar del espacio polylog?

Hsien-Chih Chang 張顯 之
fuente
Hsien-Chih, buena pregunta.
Mohammad Al-Turkistany
99
Se sabe que . Hasta donde yo sé personalmente, la relación exacta entrepolyLPPpolyLpolyLP polyLpolyL, específicamente los ejercicios y la discusión al final del Capítulo 16.
Daniel Apon
polyLP
P
P

Respuestas:

51

La clase más pequeña que contiene tiempo lineal y cerrada bajo subrutinas es P. La clase más pequeña que contiene espacio de registro y cerrada bajo subrutinas sigue siendo espacio de registro. Por lo tanto, P y L son las clases robustas más pequeñas para tiempo y espacio respectivamente, por lo que se sienten bien para modelar computación eficiente.

Lance Fortnow
fuente
44
Esta parece ser la mejor respuesta a la pregunta real formulada.
Derrick Stolee
1
Entre todas estas buenas respuestas, creo que la respuesta de Lance es la más precisa, y la aceptaré. ¡Pero aún así muchas gracias a todas las respuestas reflexivas!
Hsien-Chih Chang 張顯 之
1
Además, es un problema abierto si P = L.
Diego de Estrada
25

SPACE[log2n]Plogk1(n)NSPACE[logkn]-complete

PLOSS=kTISP[nk,klog2n]DCFLPLOSSSC2SCk

Michael Blondin
fuente
2
QuasiP=k0TIME[2logkn]P
¿Es este un problema abierto conocido? ¿Podría proporcionar una referencia?
Mohammad Al-Turkistany
SC2
55
Tenga en cuenta que SC fue nombrado por Nick Pippenger, en un supuesto acuerdo recíproco con Steve Cook para nombrar a NC después de él :)
Suresh Venkat
PPQuasiPpolyLLPSPACE[logkn]PkLk
Hsien-Chih Chang 張顯 之
20

2O(logn)=poly(n)

NSPACE[logkn]SPACE[log2kn]

SCk=TISP[poly(n),logkn]

Derrick Stolee
fuente
polyLNLpolyL
{1}
Tienes razón, perdón por la estúpida pregunta :(
Hsien-Chih Chang 張顯 之
13

Creo que todas las otras respuestas son muy buenas; Trataré de dar una perspectiva diferente sobre el tema.

No sé qué tan bien P modela la computación "eficiente" en el mundo real, pero nos gusta la clase debido a sus buenas propiedades de cierre y otras razones matemáticas. Del mismo modo, L también es una buena clase debido a algunas de las razones antes mencionadas.

Sin embargo, como usted comentó, si relajamos nuestra definición de "eficiente" al tiempo cuasi polinomial, entonces PolyL también es eficiente. Podríamos discutir la teoría de la complejidad donde permitimos que las clases definidas con un límite logarítmico en algún recurso usen recursos polylog en su lugar. En consecuencia, también relajaríamos nuestras definiciones de NC, NL, etc. para permitir en su lugar circuitos de tamaño cuasi polinomial. Si hacemos esto, NC 1 , L, NL y NC coinciden con la clase PolyL. En este sentido, PolyL es una clase robusta ya que muchas clases naturales coinciden con ella. Para obtener más información sobre la teoría de la complejidad con log -> polylog y polynomial -> cuasi-polynomial, consulte Clases de circuito de tamaño cuasipolinomial de Barrington.

Otra razón para estudiar polyL o clases similares como cuasi-AC 0 es que si bien una separación oráculo entre (digamos) ParityP y PH implica que PARITY no está contenida en AC 0 , no se sabe que la implicación inversa sea cierta. Por otro lado, PARITY no está contenido en cuasi-AC 0 si y solo si hay una separación de oráculo entre ParityP y PH. Del mismo modo, las clases cuasi-TC 0 y cuasi-AC 0 son diferentes si y solo si hay una separación de oráculo entre CH y PH. Entonces, las clases de complejidad habituales como PH, ModPH, CH, etc., cuando se reducen de forma exponencial para demostrar los resultados del oráculo, se convierten en versiones cuasi-polinomiales de las clases habituales AC 0 , ACC 0 y TC0 respectivamente. Del mismo modo, el argumento utilizado en el teorema de Toda (PH está contenido en P PP ) puede usarse para mostrar que cuasi-AC 0 está contenido en cuasi-TC 0 de profundidad-3 . (No sé si se conoce la misma conclusión para las versiones habituales de estas clases. He visto esto como un problema abierto en algunos documentos).

Robin Kothari
fuente
1
Su respuesta realmente ayuda, gracias por compartir su opinión. ¡Estoy sorprendido de que Cuasi-algo haya sido estudiado MUCHO!
Hsien-Chih Chang 張顯 之