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 .
Estoy buscando más problemas intermedios entre y N L , es decir, problemas que son:
- se sabe que está en pero no se sabe (o es poco probable) que sea N L -completo y
- conocido por ser -Hard pero no sabe que en L .
fuente
Se sabe que la coincidencia perfecta plana bipartita está en (aunque no en U L ∩ c o U L ). Dado que la accesibilidad planar se reduce a esto, es L- duro.UL UL∩coUL L
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)
fuente