Sur des ensembles complets clairsemés et P vs L

Le théorème de Mahaney nous dit que s'il y a un ensemble incomplet de clairsemé sous des réductions de plusieurs un en temps polynomial, alors . (Voir " Ensembles complets clairsemés pour NP: solution d'une conjecture de Berman et Hartmanis ")$NP$$P = NP$

Existe-t-il des conséquences connues de l'existence d'ensembles complets clairsemés pour d'autres classes de complexité? En particulier, s'il y a un ensemble complet clairsemé sous les réductions de plusieurs un de l'espace journal, cela implique-t-il ?$P$$P = L$

Oui, exactement ce que vous avez suggéré est vrai: s'il y a un ensemble clairsemé de sous des réductions de plusieurs dans l'espace journal, alors . Cela a été conjecturé par Hartmanis en 1978 et prouvé par Cai et Sivakumar en 1995. Voir cet article .$\mathbf{P}$$\mathbf{P} = \mathbf{L}$

Hartmanis a également supposé que s'il y avait un ensemble clairsemé de sous des réductions de plusieurs dans l'espace journal, alors . Cela a également été prouvé par Cai et Sivakumar en 1997; voir cet autre article .$\mathbf{NL}$$\mathbf{NL} = \mathbf{L}$