Problemas intermedios entre L y NL

26

Es bien sabido que la conectividad st dirigida es -completa. Consecuencia del avance Reingold mostró que no dirigido st-conectividad está en L . Planar dirigida st-conectividad es conocido por ser en U L c o U L . Cho y Huynh definen un problema de la mochila parametrizada y exhibieron una jerarquía de problemas entre L y N L .NLLULcoULLNL

Estoy buscando más problemas intermedios entre y N L , es decir, problemas que son:LNL

  • se sabe que está en pero no se sabe (o es poco probable) que sea N L -completo yNLNL
  • conocido por ser -Hard pero no sabe que en L .LL
Shiva Kintali
fuente

Respuestas:

13

El problema-RL completa de alcanzabilidad en grafos dirigidos con mezcla de tiempo polinómico (mostrado por Reingold, Trevisan, y Vadhan en Pseudorandom camina sobre dígrafos regulares y el problema RL vs. L ) está en el espacio (ver BPHSPACE ( S ) DSPACE ( S 3 / 2 ) por Saks y Zhou ), que es estrictamente entre L y Savitch de atado en NL de O ( log 2 n ) el espacio.log3/2(n)BPHSPACE(S)DSPACE(S3/2)O(log2n)

Derrick Stolee
fuente
10

El problema completo de RUL de accesibilidad en manglares se puede decidir en el espacio ( Allender, Lange , RUSPACE ( log n ) DSPACE ( log 2 n / log log n ) ). Un manglar es un gráfico dirigido donde hay como máximo un camino entre dos vértices.O(log2n/loglogn)RUSPACE(logn)DSPACE(log2n/loglogn)

Derrick Stolee
fuente
1
Ver también: Lange, "Una clase inequívoca que posee un conjunto completo" STACS '97.
Derrick Stolee
6

Se sabe que la coincidencia perfecta plana bipartita está en (aunque no en U Lc o U L ). Dado que la accesibilidad planar se reduce a esto, es L- duro.ULULcoULL

Ref: Samir Datta, Raghav Kulkarni, Raghunath Tewari: La coincidencia perfecta en gráficos planos bipartitos está en UL. Coloquio electrónico sobre la complejidad computacional (ECCC) 17: 201 (2010)

SamiD
fuente
Supongo que debería estar un poco avergonzado por la respuesta rancia, pero solo por el bien.
SamiD