Неконструктивные доказательства существования алгоритма
Подавляющее большинство положительных результатов по вычислительным задачам являются конструктивными доказательствами , т. е. разрешимость вычислительной задачи доказывается путем демонстрации алгоритма , который ее решает; показано, что вычислительная задача находится в P (сложность), демонстрируя алгоритм, который решает ее за время, полиномиальное по размеру входных данных; и т. д.
Однако есть несколько неконструктивных результатов, в которых доказывается существование алгоритма без демонстрации самого алгоритма. Для обеспечения таких доказательств существования используются несколько методов.
Использование неизвестного конечного множества
[ редактировать ]В комбинаторной теории игр
[ редактировать ]Простой пример неконструктивного алгоритма был опубликован в 1982 году Элвином Р. Берлекэмпом , Джоном Х. Конвеем и Ричардом К. Гаем в их книге «Пути к победе в ваших математических играх» . Речь идет об игре Sylver Coinage , в которой игроки по очереди указывают положительное целое число, которое не может быть выражено в виде суммы ранее указанных значений, при этом игрок проигрывает, когда его заставляют указать число 1. Существует алгоритм (приведенный в книга в виде блок-схемы) для определения того, является ли данный первый ход выигрышным или проигрышным: если это простое число больше трех или одно из конечного набора 3-гладких чисел , то это выигрышный первый ход, и в противном случае он проигрывает. Однако конечное множество неизвестно.
В теории графов
[ редактировать ]Неконструктивные доказательства алгоритмов для задач теории графов изучались, начиная с 1988 года, Майклом Феллоузом и Майклом Лэнгстоном . [1]
Общий вопрос в теории графов заключается в том, обладает ли определенный входной граф определенным свойством. Например:
- Входные данные: граф G .
- Вопрос: Можно ли вложить G в трехмерное пространство так, чтобы никакие два непересекающихся цикла G не были топологически связаны (как в звеньях цепи)?
Существует высокоэкспоненциальный алгоритм, который решает, связаны ли два цикла, встроенные в трехмерное пространство, и можно проверить все пары циклов в графе, но не очевидно, как учесть все возможные вложения в трехмерное пространство. Таким образом, априори вообще не ясно, разрешима ли проблема связанности.
Однако существует неконструктивное доказательство, показывающее, что связанность разрешима за полиномиальное время. Доказательство опирается на следующие факты:
- Множество графов, для которых ответ «да», замкнуто при взятии миноров . То есть, если граф G можно вложить без зацеплений в трехмерное пространство, то каждый минор графа G также можно вложить без зацеплений.
- Для любых двух графов G и H можно за полиномиальное время определить, является ли H минором G .
- По теореме Робертсона-Сеймура любой набор конечных графов содержит только конечное число минорно-минимальных элементов. В частности, множество экземпляров «да» имеет конечное число второстепенных-минимальных элементов.
Учитывая входной граф G , следующий «алгоритм» решает вышеуказанную проблему:
- Для каждого минорно-минимального элемента H :
- Если H является минорным по отношению к G , верните «да».
- верните «нет».
- Для каждого минорно-минимального элемента H :
Неконструктивная часть здесь — это теорема Робертсона–Сеймура. Хотя он гарантирует, что существует конечное число минорных-минимальных элементов, он не говорит нам, что это за элементы. Следовательно, мы не можем реально реализовать упомянутый выше «алгоритм». Но мы знаем, что алгоритм существует и что время его выполнения полиномиально.
Существует еще много подобных задач, разрешимость которых можно доказать аналогичным образом. В некоторых случаях знание того, что проблема может быть доказана за полиномиальное время, побудило исследователей искать и найти реальный алгоритм с полиномиальным временем, который решает проблему совершенно другим способом. Это показывает, что неконструктивные доказательства могут иметь конструктивные результаты. [1]
Основная идея состоит в том, что задачу можно решить с помощью алгоритма, использующего в качестве параметра неизвестное множество. Хотя набор неизвестен, мы знаем, что он должен быть конечным, и, следовательно, существует алгоритм с полиномиальным временем.
Существует множество других комбинаторных задач, которые можно решить с помощью аналогичного метода. [2]
Подсчет алгоритмов
[ редактировать ]Иногда число потенциальных алгоритмов для данной задачи конечно. Мы можем подсчитать количество возможных алгоритмов и доказать, что только ограниченное число из них «плохие», поэтому хотя бы один алгоритм должен быть «хорошим».
В качестве примера рассмотрим следующую проблему. [3]
Я выбираю вектор v, состоящий из n элементов, которые являются целыми числами от 0 до определенной константы d .
Вы должны угадать v, задав запросы суммы , которые представляют собой запросы вида: «Какова сумма элементов с индексами i и j ?». Запрос суммы может относиться к любому количеству индексов от 1 до n .
Сколько запросов вам нужно? Очевидно, что n запросов всегда достаточно, потому что вы можете использовать n запросов, запрашивающих «сумму» одного элемента. Но когда d достаточно мало, можно добиться большего. Общая идея заключается в следующем.
Каждый запрос может быть представлен как вектор размером 1 на n , все элементы которого находятся в наборе {0,1}. Ответ на запрос — это просто скалярное произведение вектора запроса на v . Каждый набор из k запросов может быть представлен матрицей над { k -n 0,1}; набор ответов является произведением матрицы на v .
Матрица M является «хорошей», если она позволяет нам однозначно идентифицировать v . Это означает, что для каждого вектора v произведение M v уникально. Матрица M является «плохой», если существуют два разных вектора, v и u , такие, что M v = M u .
Используя некоторую алгебру, можно ограничить количество «плохих» матриц. Граница является функцией d и k . Таким образом, для достаточно малого d должна существовать «хорошая» матрица с малым k , что соответствует эффективному алгоритму решения задачи идентификации.
Это доказательство неконструктивно по двум причинам: неизвестно, как найти хорошую матрицу; и даже если предоставлена хорошая матрица, неизвестно, как эффективно восстановить вектор из ответов на запросы.
Есть еще много подобных задач, которые, как можно доказать, можно решить аналогичным способом. [3]
Дополнительные примеры
[ редактировать ]- Можно показать, что некоторые вычислительные проблемы разрешимы с помощью закона исключенного третьего . Такие доказательства обычно не очень полезны на практике, поскольку связанные с ними проблемы весьма искусственны.
- Пример из квантовой теории сложности (связанный со сложностью квантовых запросов ) приведен в. [4]
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б Товарищи, MR; Лэнгстон, Массачусетс (1988). «Неконструктивные инструменты доказательства разрешимости за полиномиальное время» . Журнал АКМ . 35 (3): 727. дои : 10.1145/44483.44491 . S2CID 16587284 .
- ^ Браун, диджей; Товарищи, MR; Лэнгстон, Массачусетс (2007). «Самосводимость за полиномиальное время: теоретические мотивы и практические результаты *». Международный журнал компьютерной математики . 31 (1–2): 1–9. дои : 10.1080/00207168908803783 .
- ↑ Перейти обратно: Перейти обратно: а б Гребинский В.; Кучеров, Г. (2000). «Оптимальная реконструкция графов по аддитивной модели» (PDF) . Алгоритмика . 28 : 104–124. дои : 10.1007/s004530010033 . S2CID 33176053 .
- ^ Киммел, С. (2013). «Квантовый противник (верхняя) граница». Чикагский журнал теоретической информатики . 19 : 1–14. arXiv : 1101.0797 . дои : 10.4086/cjtcs.2013.004 . S2CID 119264518 .
Кредиты
[ редактировать ]Ссылки на этой странице были собраны из следующих тем Stack Exchange :
- «Существуют ли проблемы без эффективных алгоритмов, где теоремы существования доказали, что такие алгоритмы должны существовать?» . Обмен стеками теории CS . Проверено 21 ноября 2014 г.
- «Существуют ли неконструктивные доказательства существования алгоритма?» . Обмен стеками теории CS . Проверено 21 ноября 2014 г.
- «Существует ли алгоритм, который доказуемо существует, хотя мы не знаем, что это такое?» . Обмен стеками в области компьютерных наук . Проверено 21 ноября 2014 г.