patternMinor
Complexity class that properly included in DLOGTIME
Viewed 0 times
properlythatincludeddlogtimeclasscomplexity
Problem
Is there any decision problem that is in a complexity class properly included in DLOGTIME? (except $O(1)$, of course)
If there is, can we create complete problems for DLOGTIME? So, can there be reduction by $O(\log(\log n))$ or smaller?
If there is, can we create complete problems for DLOGTIME? So, can there be reduction by $O(\log(\log n))$ or smaller?
Solution
Regan & Vollmer suggest in the conclusion of the linked paper that such classes are constructible (though fiddly). The paper itself is about LOGTIME, and mentions where changes have to be made to adapt the results to LOGLOGTIME, LOGLOGLOGTIME etc., but don't explicitly demonstrate the results.
Context
StackExchange Computer Science Q#2221, answer score: 3
Revisions (0)
No revisions yet.