ДЛИТЕЛЬНОЕ ВРЕМЯ
-
Определение класса сложности DLOGTIME
- DLOGTIME включает задачи, решаемые за логарифмическое время на детерминированной машине Тьюринга.
- Машина Тьюринга с произвольным доступом используется для определения класса сложности, так как длина ленты превышает доступное пространство.
-
Слабость модели
- Ни одна машина Тьюринга с меньшим детерминированным ограничением времени не может обработать все входные данные.
-
Примеры задач в DLOGTIME
- Примеры задач включают проверку длины входных данных, например, определение четности длины.
-
Применение в информатике
- Равномерность времени ожидания важна для сложности схем.
-
Рекомендации
- Статья является заглушкой и нуждается в расширении для Википедии.
Полный текст статьи: