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