En conjuntos completos escasos y P vs L

Teorema de Mahaney nos dice que si hay una escasa conjunto -Complete bajo en tiempo polinomial muchos uno-reducciones, entonces P = N P . (Ver " Conjuntos completos escasos para NP: Solución de una conjetura de Berman y Hartmanis ")$NP$$P = NP$

¿Existen consecuencias conocidas de la existencia de conjuntos completos dispersos para otras clases de complejidad? En particular, si hay un conjunto completo de escaso bajo reducciones de espacio de registro de muchos, ¿eso implica P = L ?$P$$P = L$

Sí, exactamente lo que usted sugiere es cierto: si hay una escasa conjunto -Complete bajo registro en el espacio muchos uno-reducciones, entonces P = L . Hartmanis conjeturó esto en 1978 y Cai y Sivakumar lo probaron en 1995. Vea este documento .$\mathbf{P}$$\mathbf{P} = \mathbf{L}$

Hartmanis también conjeturó que si hay una escasa conjunto -Complete bajo log-espacio muchos uno-reducciones, entonces N L = L . Esto también fue demostrado por Cai y Sivakumar en 1997; Mira este otro artículo .$\mathbf{NL}$$\mathbf{NL} = \mathbf{L}$