Classe de complexidade que foi incluída corretamente no DLOGTIME

8

Existe algum problema de decisão em uma classe de complexidade incluída corretamente no DLOGTIME? (exceto , é claro)O(1)

Se houver, podemos criar problemas completos para o DLOGTIME? Então, pode haver redução em ou menor?O(log(logn))

user2346
fonte

Respostas:

3

Regan & Vollmer sugerem na conclusão do artigo vinculado que tais classes são construtíveis (embora minuciosas). O artigo em si é sobre LOGTIME, e menciona onde mudanças devem ser feitas para adaptar os resultados a LOGLOGTIME, LOGLOGLOGTIME etc., mas não demonstram explicitamente os resultados.

Luke Mathieson
fonte