Komplexitätsklasse, die ordnungsgemäß in DLOGTIME enthalten ist

8

Gibt es ein Entscheidungsproblem in einer Komplexitätsklasse, die ordnungsgemäß in DLOGTIME enthalten ist? (außer natürlich)O(1)

Wenn ja, können wir vollständige Probleme für DLOGTIME erstellen? Kann es also eine Reduzierung um oder kleiner geben?O(log(logn))

user2346
quelle

Antworten:

3

Regan & Vollmer schlagen in der Schlussfolgerung des verlinkten Papiers vor, dass solche Klassen konstruierbar sind (wenn auch fummelig). Das Papier selbst befasst sich mit LOGTIME und erwähnt, wo Änderungen vorgenommen werden müssen, um die Ergebnisse an LOGLOGTIME, LOGLOGLOGTIME usw. anzupassen, demonstriert die Ergebnisse jedoch nicht explizit.

Luke Mathieson
quelle