Lower Bound

Lower bound (нижняя граница, нижняя оценка) — в математике, информатике и теории сложности вычислений это функция или число, которое является минимально возможным значением для некоторой величины в заданном классе задач или алгоритмов. Понятие нижней границы противопоставляется верхней границе (upper bound) и используется для доказательства того, что никакой алгоритм не может решить задачу быстрее или с меньшими ресурсами, чем указанная граница.

Определение и основные понятия

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

Различают два основных типа нижних границ:

• Асимптотическая нижняя граница — записывается в нотации Ω (большая омега). Например, Ω(n log n) означает, что для любого алгоритма существует бесконечно много входов, на которых время выполнения не меньше, чем c·n log n для некоторой константы c.
• Точная нижняя граница — конкретное число, например, для сортировки сравнением минимальное количество сравнений равно ⌈log₂(n!)⌉.

История развития понятия

Идея нижних границ восходит к работам Джона фон Неймана и Алана Тьюринга в 1930-х годах, когда они заложили основы теории сложности вычислений. Однако систематическое изучение нижних границ началось в 1960-х годах с развитием теории алгоритмов.

В 1965 году Юрий Матиясевич доказал, что не существует алгоритма для решения диофантовых уравнений, что стало одним из первых примеров неразрешимости. В 1971 году Стивен Кук сформулировал проблему P vs NP, которая напрямую связана с поиском нижних границ для задач из класса NP.

В 1980-х годах появились методы доказательства нижних границ, основанные на теории коммуникационной сложности (Эндрю Яо, 1979) и на теории верификации (Ласло Бабаи, 1985). В 1990-х годах Александр Разборов и Стивен Рудич разработали метод естественных доказательств, который показал ограничения существующих подходов к доказательству нижних границ для схем.

Классификация нижних границ

По области применения

• Вычислительные нижние границы — минимальное время или число шагов для решения задачи на машине Тьюринга или в модели RAM.
• Коммуникационные нижние границы — минимальное количество бит, которое необходимо передать между участниками для решения задачи.
• Схемные нижние границы — минимальный размер или глубина булевой схемы, вычисляющей заданную функцию.
• Пространственные нижние границы — минимальный объём памяти, необходимый для решения задачи.

По строгости

• Асимптотические нижние границы — описывают поведение функции при стремлении аргумента к бесконечности (Ω-нотация).
• Точные нижние границы — конкретные числа для фиксированных размеров входа.
• Условные нижние границы — зависят от недоказанных гипотез (например, P ≠ NP).

Методы доказательства нижних границ

Метод противника (adversary argument)

Этот метод заключается в построении «противника», который отвечает на запросы алгоритма таким образом, чтобы вынудить его выполнить как можно больше операций. Классический пример — доказательство нижней границы для поиска максимума в неупорядоченном массиве: любой алгоритм должен выполнить не менее n-1 сравнений.

Метод перебора всех возможных вариантов

Используется для задач, где количество возможных исходов ограничено. Например, для сортировки сравнением существует n! возможных перестановок, и каждое сравнение может дать только два результата, поэтому необходимо не менее ⌈log₂(n!)⌉ сравнений.

Метод сведения (reduction)

Если задача A сводится к задаче B, то нижняя граница для A переносится на B. Например, если задача умножения матриц сводится к задаче умножения чисел, то нижняя граница для умножения матриц не может быть меньше, чем для умножения чисел.

Метод булевых схем

Используется для доказательства нижних границ размера схем. Один из подходов — показать, что функция имеет высокую степень полинома над конечным полем или что её нельзя вычислить схемой малого размера из-за ограничений на количество переменных.

Примеры нижних границ

Сортировка сравнением

Для сортировки n элементов с помощью сравнений нижняя граница составляет Ω(n log n) операций. Это следует из того, что количество возможных перестановок равно n!, а каждое сравнение даёт не более двух исходов. Точная нижняя граница для n=3 составляет 3 сравнения, для n=4 — 5 сравнений, для n=5 — 7 сравнений.

Поиск в упорядоченном массиве

Для поиска элемента в упорядоченном массиве размера n нижняя граница составляет Ω(log n) сравнений. Это достигается бинарным поиском, который выполняет ровно ⌈log₂(n+1)⌉ сравнений в худшем случае.

Умножение матриц

Для умножения двух матриц размера n×n нижняя граница составляет Ω(n²) операций, так как результат содержит n² элементов. Однако точная нижняя граница для алгоритмов, использующих только умножение и сложение, неизвестна. Наилучший известный алгоритм (Копперсмит-Виноград, 1987) имеет сложность O(n²·376), но нижняя граница Ω(n²) не достигнута.

Вычисление определителя

Для вычисления определителя матрицы n×n нижняя граница составляет Ω(n²) операций, так как результат зависит от n² элементов. Однако существуют алгоритмы со сложностью O(n³) (метод Гаусса), а нижняя граница Ω(n²) не является строгой, так как неизвестно, можно ли вычислить определитель быстрее.

Применение в информатике

Теория сложности вычислений

Нижние границы используются для классификации задач по сложности. Например, если для задачи доказана нижняя граница Ω(2ⁿ), то она не может быть решена за полиномиальное время, что относит её к классу экспоненциально сложных.

Криптография

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

Проектирование алгоритмов

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

Вычислительная биология

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

Ограничения и нерешённые проблемы

Проблема P vs NP

Одна из главных нерешённых проблем в теории сложности — доказательство нижней границы для задач из класса NP. Если будет доказано, что для некоторой NP-полной задачи нижняя граница превышает полиномиальную, то это будет означать, что P ≠ NP. Однако пока не удалось доказать даже суперлинейных нижних границ для NP-полных задач в общей модели вычислений.

Метод естественных доказательств

В 1994 году Разборов и Рудич показали, что многие методы доказательства нижних границ для схем не могут быть использованы для доказательства нижних границ для NP-полных задач, если только не нарушаются некоторые криптографические предположения. Это ограничение существенно затрудняет поиск нижних границ.

Проблема нижних границ для умножения

Точная нижняя граница для умножения двух n-битных чисел неизвестна. Наилучшая известная нижняя граница составляет Ω(n log n) (по теореме Шёнхаге-Штрассена), но лучший алгоритм (Фюрер, 2007) имеет сложность O(n log n · 2^{O(log* n)}). Неизвестно, можно ли умножать числа за линейное время.

Интересные факты

• Нижняя граница для сортировки сравнением была впервые доказана в 1956 году Джоном фон Нейманом в контексте анализа сортировки слиянием.
• В 1972 году Майкл Рабин доказал, что для поиска максимума в массиве из n элементов необходимо не менее n-1 сравнений, что является точной нижней границей.
• Для задачи умножения матриц нижняя граница Ω(n²) была доказана в 1969 году, но до сих пор не удалось доказать, что нельзя умножать матрицы быстрее, чем за O(n²·376).
• В 2015 году Ласло Бабаи и его коллеги доказали нижнюю границу Ω(n log n) для задачи проверки изоморфизма графов в модели, где алгоритм может задавать вопросы только о смежности вершин.

Источники

• Ахо А., Хопкрофт Дж., Ульман Дж. «Структуры данных и алгоритмы». — М.: Вильямс, 2000.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ». — 3-е изд. — М.: Вильямс, 2013.
• Разборов А. А. «Нижние оценки сложности булевых схем». — М.: МЦНМО, 2005.
• Стивен Кук. «Сложность вычислений». — Лекции, 2000.
• Юрий Матиясевич. «Десятая проблема Гильберта». — М.: Наука, 1993.