Реально ли доказать нижние оценки?

Учитывая любую вычислительную проблему, является ли задача нахождения нижних границ для такого вычисления действительно возможной? Я полагаю, что все сводится к тому, как определяется один вычислительный шаг и какую модель мы используем для доказательства, но, учитывая это, действительно ли мы докажем нижнюю границу, тогда вообще? Я имею в виду, что мы можем доказать что-то вроде «проблема не может быть решена быстрее, чем время », а не «проблема может быть решена за время или быстрее»? $X$ $t(X)$ $X$ $t(X)$

Я пытался найти информацию конкретно о нижних границах и доказательствах их, но я не могу найти какой-либо интерес, какие-либо рекомендации по книгам / работам / веб-сайтов по этому вопросу?

complexity-theory time-complexity proof-techniques lower-bounds hsalin
источник

Ответы:

Мы можем абсолютно доказать такие вещи.

Многие задачи имеют тривиальные нижние границы, например, нахождение минимума из набора из чисел (которые никоим образом не отсортированы / не структурированы) занимает не менее времени. Доказательство этого простое: гипотетический алгоритм, который выполняется за время, не может проверить все числа на входе. Таким образом, если мы запустили алгоритм на каком-либо входе, мы могли бы заметить, что он никогда не проверял определенный элемент ввода. Изменяя этот элемент до минимума, мы можем заставить алгоритм потерпеть неудачу. $n$ $\Omega(n)$ $o(n)$

Менее тривиальной нижней границей является нижняя граница для сортировки в модели, основанной на сравнении. Доказательство этого заключается в следующем: с учетом ввода чисел существует возможные выходы (вход может быть любой перестановкой отсортированного списка, поэтому выход также может быть любой перестановкой ввода). Если мы ограничены только выполнением сравнений, то нашему алгоритму (в среднем) необходимо выполнить как минимум сравнений, чтобы иметь возможность дать $\Omega(n \log n)$ $n$ $n!$ $\log_2(n!)=\Omega(n \log n)$ разные выходы. $n!$

Нижние границы могут быть еще сильнее. Существует несколько проблем (в частности, трудные задачи), для которых существует экспоненциальная нижняя оценка. Проблемы в этом классе включают вычисление оптимальных стратегий для таких игр, как (обобщенные) шахматы, шашки и го. Доказательством этого является теорема об иерархии времени , в которой говорится (с некоторыми ограничениями на ): $EXPTIME$ $f$

Для данной функции существует вычислительная задача, которая может быть решена за время но не может быть решена за время $f$ $O(f(n))$ . $o(\frac{f(n)}{\log n})$

Таким образом, в принципе, если вы можете думать о функции существует проблема, которая требует столько времени для ее решения. $f$

Наконец, еще один способ не обязательно доказать нижнюю границу времени, но что-то еще более сильное, показывает неразрешимость проблемы (например, остановка, переписка).

Том ван дер Занден
источник

Размер ввода или вывода являются наиболее распространенными нижними границами.

Рафаэль

$\Omega(n\log n)$ $n$

$O(n\log n)$

L \subseteq N L \subseteq P \subseteq N P \subseteq P S P A C E,

$\mathrm{L}\subseteq \mathrm{NL}\subseteq \mathrm{P}\subseteq \mathrm{NP} \subseteq\mathrm{PSPACE}\,,$

L \subset P S P A C E

$\mathrm{L}\subset \mathrm{PSPACE}$

С другой стороны, у Райана Уильямса есть хорошая статья (и речь, которую я слышал пару раз) под названием « Алгоритмы для схем и схемы для алгоритмов» , в которой он утверждает, что нахождение нижних границ и нахождение алгоритмов не являются принципиально что отличается. Например, он приводит доказательство неразрешимости проблемы остановки как пример алгоритма (универсальной машины Тьюринга), который используется именно для доказательства нижней границы (неразрешимости).

Дэвид Ричерби
источник

Я думаю, что это то, что мне нужно: «вам как-то нужно показать, что ни один алгоритм в определенном классе не может решить вашу проблему», это та часть, которую я нахожу немного сбивающей с толку, поскольку я не могу по-настоящему интуитивно понять, как можно это сделать. такая вещь, в общем как минимум. Как @Tom van der Zanden описал найденное минимальное число, которое я понимаю, но является ли этот подход общим? Я имею в виду общее, как наличие такого рода аргументов при построении доказательств? Спасибо за ссылку.

hsalin

@ user1288420 Ты не один. Если бы кто-нибудь мог интуитивно понять, как доказать, что ни один алгоритм в определенном классе не может решить какую-то проблему, у нас было бы намного больше нижних результатов! Как правило, вам нужно придумать какое-то свойство, которое есть у каждого алгоритма в классе, и показать, что это свойство предотвращает решение некоторой проблемы. Например, каждая машина Тьюринга, работающая в сублинейное время, обладает свойством, которое она не может даже прочитать все свои входные данные. Это означает, что это не может решить большинство проблем. Это тривиально; к сожалению, более интересные случаи кажутся невероятно сложными.

Дэвид Ричерби

$n$

Однако в этом вопросе есть пункт, который требует еще нескольких замечаний относительно нижней границы (или границ сложности в целом).

На самом деле выбор того, что является одним вычислительным шагом, не имеет значения, поскольку вычислительные шаги могут рассматриваться как имеющие постоянную верхнюю границу (и нижнюю границу). Результат сложности будет таким же, так как он определен с точностью до константы. Принятие 3 сравнений в качестве единичных операций или только одного, не имеет значения.

То же самое относится и к размеру данных, который служит ссылкой для оценки стоимости вычислений. Принимая одно целое или два целых в качестве единицы размера не имеет значения.

Тем не менее, два варианта должны быть связаны.

$n$ $\log n$ $O(\log n)$

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

Babou
источник

Поиск всех вхождений шаблона в строке тривиально требует чтения всей строки: если шаблон является «a», вы не можете найти все вхождения, не проверив наличие каждого отдельного символа строки.

Дэвид Ричерби

@DavidRicherby На самом деле не всегда. Алгоритм Бойера-Мура начинается с конца паттерна, таким образом подпрыгивая в цепочке. Если попытка совпадения не удалась, ему не нужно читать начало строки. Кроме того, он имеет оптимизацию, аналогичную алгоритму Кнута-Морриса-Пратта, для пропуска попыток, которые обречены на неудачу из-за структуры шаблона. Конечно, есть шаблоны, которые требуют чтения всей строки.

Бабу

@DavidRicherby Почему ты спросил, ты знал это?

Бабу

Я не понимаю ваш второй комментарий. Ваш первоначальный ответ содержал неверную заявку. Конечно, я знал, что это неправильно: вот как я мог это указать! Другие люди, возможно, не знали, что это неправильно, поэтому им было бы непонятно оставить ответ таким, какой он был.

Дэвид Ричерби,

@DavidRicherby Моя точка зрения, вы поняли, что я имел в виду. Я должен был сказать, что нет, а не нет . Это не требовало стиля комментария, заставляющего читателей верить, что я говорю чепуху. И при этом вы совершили точно такую же неосторожную ошибку: заявив « Поиск всех вхождений шаблона в строке тривиально требует чтения всей строки », когда вы должны были сказать « Поиск всех вхождений шаблона в строке может потребовать чтение всей строки ". Я только хотел заявить, что чтение входных данных не всегда необходимо, чтобы смягчить мой предыдущий пример.

Бабу