WikiDer > DLOGTIME

DLOGTIME

В теория сложности вычислений, DLOGTIME это класс сложности из всех вычислительные проблемы разрешима в логарифмический количество время вычисления на детерминированном Машина Тьюринга. Он должен быть определен на машина Тьюринга с произвольным доступом, так как в противном случае входная лента длиннее, чем диапазон ячеек, к которым машина может получить доступ. Это очень слабая модель временной сложности: никакая машина Тьюринга с произвольным доступом с меньшей детерминированной временной границей не может получить доступ ко всему входу.[1]

DLOGTIME-единообразие важно в сложность схемы.[1][2]

Рекомендации

  1. ^ а б Джонсон, Дэвид С. (1990), "Каталог классов сложности", Справочник по теоретической информатике, Vol. А, Elsevier, Амстердам, стр. 67–161, МИСТЕР 1127168. См. В частности п. 140.
  2. ^ Аллендер, Эрик; Гор, Вивек (1993), «О сильном отделении от переменного тока.0", Достижения в теории сложности вычислений (Нью-Брансуик, Нью-Джерси, 1990), DIMACS Ser. Дискретная математика. Теорет. Comput. Наук, 13, Амер. Математика. Soc., Providence, RI, стр. 21–37, МИСТЕР 1255326. См. В частности п. 23.