В теории сложности вычислений , DLOGTIME является классом сложности всех вычислительных задач решаемых в логарифмическом количестве времени вычислений на детерминированной машине Тьюринга . Он должен быть определен на машине Тьюринга с произвольным доступом , поскольку в противном случае входная лента длиннее, чем диапазон ячеек, к которым машина может получить доступ. Это очень слабая модель временной сложности: никакая машина Тьюринга с произвольным доступом с меньшей детерминированной временной границей не может получить доступ ко всему входу. [1]
Примеры
DLOGTIME включает задачи, связанные с проверкой длины ввода, [1] например, проблему « Имеет ли ввод четной длины? », Которая может быть решена за логарифмическое время с использованием двоичного поиска .
Приложения
DLOGTIME - единообразие важно в сложности схемы . [1] [2]
Рекомендации
- ^ a b c Джонсон, Дэвид С. (1990), "Каталог классов сложности", Справочник по теоретической информатике, Vol. A , Elsevier, Amsterdam, стр. 67–161, MR 1127168.. См., В частности, стр. 140 .
- ^ Аллендер, Эрик; Гор, Вивек (1993), "О сильных отделениях от AC 0 ", Успехи в теории вычислительной сложности (Нью-Брансуик, Нью-Джерси, 1990) , DIMACS Ser. Дискретная математика. Теорет. Comput. Наук, 13 , амер. Математика. Soc., Providence, RI, стр. 21–37, MR 1255326. См., В частности, стр. 23 .