Clase de complejidad que se incluye correctamente en DLOGTIME

8

¿Hay algún problema de decisión que se encuentre en una clase de complejidad incluida correctamente en DLOGTIME? (exceptoO(1), por supuesto)

Si es así, ¿podemos crear problemas completos para DLOGTIME? Entonces, ¿puede haber una reducción porO(Iniciar sesión(Iniciar sesiónnorte)) o más pequeño?

usuario2346
fuente

Respuestas:

3

Regan y Vollmer sugieren en la conclusión del artículo vinculado que tales clases son construibles (aunque fiddly). El documento en sí trata sobre LOGTIME y menciona dónde se deben hacer cambios para adaptar los resultados a LOGLOGTIME, LOGLOGLOGTIME, etc., pero no demuestre explícitamente los resultados.

Luke Mathieson
fuente