Classe de complexité correctement incluse dans DLOGTIME

8

Existe-t-il un problème de décision dans une classe de complexité correctement incluse dans DLOGTIME? (saufO(1), bien sûr)

Si tel est le cas, pouvons-nous créer des problèmes complets pour DLOGTIME? Alors, peut-il y avoir une réduction deO(Journal(Journaln)) ou plus petit?

user2346
la source

Réponses:

3

Regan & Vollmer suggèrent dans la conclusion de l'article lié que ces classes sont constructibles (bien que délicates). Le document lui-même concerne LOGTIME et mentionne où des changements doivent être apportés pour adapter les résultats à LOGLOGTIME, LOGLOGLOGTIME etc., mais ne démontrent pas explicitement les résultats.

Luke Mathieson
la source