Классы сложности для случаев, отличных от «наихудшего случая»

Есть ли у нас классы сложности, скажем, относительно средней сложности? Например, существует ли (именованный) класс сложности для задач, решение которых занимает ожидаемое полиномиальное время?

Другой вопрос рассматривает сложность наилучшего случая , приведенную ниже.

Есть ли класс (естественных) проблем, решение которых требует хотя бы экспоненциального времени?

Для уточнения, рассмотрим некоторые EXP -полным языка . Очевидно, что не все экземпляры требуют экспоненциального времени: существуют случаи, которые могут быть решены даже за полиномиальное время. Таким образом, лучший вариант сложности L не экспоненциальное время.$L$$L$$L$

РЕДАКТИРОВАТЬ: Поскольку возникли некоторые неясности, я хочу попытаться прояснить это еще больше. Под сложностью «в лучшем случае» я имею в виду класс сложности, сложность задач которого ограничена некоторой функцией снизу . Например, определите BestE как класс языков, который не может быть определен во времени меньше, чем некоторая линейная экспонента. Символически, пусть $M$ обозначает произвольную машину Тьюринга, а $c$ , $n_0$ и $n$ - натуральные числа:

$L \in \mathbf{BestE} \Leftrightarrow$ $\quad (\exists c)(\forall M)[(L(M) = L) \Rightarrow (\exists {n_0})(\forall n > {n_0})(\forall x \in {\{0,1\}^n})[T(M(x)) \ge {2^{c|x|}}]]$

где $T(M(x))$ обозначает время, за которое $M$ останавливается на входе $x$ .

Я принимаю, что определение такого класса задач очень странно, поскольку мы требуем, чтобы каждая машина Тьюринга $M$ , независимо от ее мощности, не могла определять язык во времени меньше, чем некоторая линейная экспонента.

Тем не менее, обратите внимание, что аналог полиномиального времени ( BestP ) является естественным, поскольку каждая машина Тьюринга требует времени $|x|$по крайней мере, прочитать его вход.

PS: Возможно, вместо количественного определения «для всей машины Тьюринга », мы должны ограничить его некоторым заранее заданным классом машин Тьюринга, таким как машины Тьюринга за полиномиальное время. Таким образом, мы можем определить классы, такие как , то есть класс языков, требующих по крайней мере квадратичного времени для выбора машин Тьюринга за полиномиальное время.B e s t ( n 2$M$$\mathbf{Best(n^2)}$

PS2: Можно также рассмотреть аналог сложности схемы, в котором мы учитываем наименьший размер / глубину цепи для выбора языка.

Хотя я не могу разобрать ваши определения, вы должны знать, что известны гораздо более сильные временные иерархии, в частности временные иерархии «почти везде».

Вот формальное утверждение: для каждой временной привязки существует язык со свойством, что каждый детерминированный алгоритм, который правильно распознает должен работать во времени, асимптотически превышающем на всех входах, кроме конечного числа, в течение достаточно малого времени . L ∈ T I M E [ T ( n ) $T(n)$$L \in TIME[T(n)]$$L$$t(n)$$t(n)$

«Достаточно маленький» означает .$t(n) \log t(n) \leq o(T(n))$

Предположим , что мы выберем для примера, и получить жесткий язык . Тогда любой алгоритм, который правильно распознает должен занимать как минимум времени на всех входах после определенной длины. Кажется, это то, что вы ищете в своем классе BestE. L L 2 n / n $T(n)=2^n$$L$$L$$2^n/n^2$

Ссылка:

John G. Geske, Dung T. Huynh, Joel I. Seiferas: заметка о почти повсеместно сложных комплексах и разделении классов детерминированной сложности времени Inf. Вычи. 92 (1): 97-104 (1991)

Есть ряд классов, которые пытаются решить различные понятия средней сложности. В Зоопарке Сложности некоторые классы, которые могут вас заинтересовать:

AvgP

HeurP

DistNP

(НП, Р-samplable)

Arora / Barak охватывает множество похожих классов (в гл. 18), определяющих distP, distNP и sampNP.

Точные отношения между всеми этими классами характеризуются пятью мирами Импальяццо, о которых ранее задавался другой вопрос .

Что касается вопроса сложности «лучший случай», я не уверен, что понимаю, что вы имеете в виду. Вы ищете EXP ?

Если вы имеете в виду классы сложности, определенные в терминах наилучшего времени выполнения для всех экземпляров, это априори не очень хорошая мера сложности, поскольку вы будете рассматривать только тривиальные случаи любой данной проблемы.

[Расширяя ответ Райана Уильямса и добавляя несколько поисковых терминов для вас] У вашего понятия о сложности наилучшего случая уже есть название: жесткость почти везде (а.е.) или би-иммунитет. (Примером Райана является -би-иммунитет). Если является классом сложности, то язык является -иммунным, если не существует бесконечного подмножества такого, что . является -би-иммунным, если и его дополнение являютсяC L C L ' ⊆ L L ' ∈ C L C L ················· L = Е * ∖ L С B E сек т Е$TIME[T(n)]$$\mathcal{C}$$L$$\mathcal{C}$$L' \subseteq L$$L' \in \mathcal{C}$$L$$\mathcal{C}$$L$$\overline{L} = \Sigma^* \backslash L$$\mathcal{C}$-immune. Например, нетрудно показать, что ваше определение эквивалентно классу -bi-иммунных наборов.$\mathbf{BestE}$$E$

(За исключением исторического: понятие иммунитета было впервые разработано Постом в 1944 году в теории вычислимости задолго до того, как П. даже был определен. Пост фактически рассматривал «простые множества» - множество простое, если его дополнение неуязвимо. Для теоретика вычислимости, слово «иммунитет» обычно означает «невосприимчивый к вычислимым наборам». В этом случае иммунитет эквивалентен «иммунитету к множествам се», поскольку каждый бесконечный набор се содержит бесконечный вычислимый. Я полагаю, что статья Поста была также первой, в которой Понятие о сокращении многие-один, но я не мог поклясться в этом.)

Разные случаи имеют больше смысла, когда речь идет об алгоритмах, а не проблемах. С другой стороны, классы сложности - это проблемы, а не алгоритмы. Следовательно, класс сложности, всегда являющийся наихудшим случаем для любого алгоритма, обусловлен определением.

По своей сложности ваша цель - узнать количество ресурсов, необходимых для решения любого случая данной проблемы. Следовательно, вы знаете, что для любого данного экземпляра и алгоритма вам понадобятся эти ресурсы и ничего более.

В анализе алгоритмов ваша цель - обеспечить, чтобы ваш алгоритм имел верхнюю границу для ресурса в любом случае проблемы. Тривиальная оценка - это класс сложности задачи, поскольку ни один полезный (тот, который делает ненужные шаги) алгоритм не требует больше времени, чем этот. Однако вы можете улучшить эту оценку, учитывая специфику алгоритма.

Например, предположим, что вы анализируете сортировку слиянием. Учитывая решение, вы можете подтвердить его за полиномиальное время, поэтому СОРТИРОВКА в НП. Однако, проанализировав, вы можете уменьшить это значение до (n * logn)$\Theta$

В лучшем случае для каждой задачи тривиально найти наименьшее количество необходимых ресурсов. Предположим, что длина ввода O (n), а длина O (m). Тогда следующий TM M всегда работает в O (n) + O (m) для лучшего случая:

М {ввода, например, решение}

1. Сравните данный экземпляр с экземпляром, закодированным в машине.
2. Если они равны, верните закодированное решение.
3. Еще, сделайте поиск грубой силы.

Кажется, что каждая задача имеет сложность наилучшего случая. Рассмотрим алгоритм, который всегда выводит решение для конкретного экземпляра. Этот случай - лучший случай.$O(1)$