Доказательства существования неконструктивных алгоритмов - Non-constructive algorithm existence proofs

Подавляющее большинство положительных результатов о вычислительные проблемы находятся конструктивные доказательства, т. е. доказывается разрешимость вычислительной задачи путем показа алгоритм что решает это; показано, что вычислительная проблема заключается в P (сложность) показав алгоритм, который решает его за время, полиномиальное по размеру входных данных; и Т. Д.

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

Использование неизвестного конечного множества

В комбинаторной теории игр

Простой пример неконструктивного алгоритма был опубликован в 1982 г. Элвин Р. Берлекамп, Джон Х. Конвей, и Ричард К. Гай, в их книге Выигрышные способы для ваших математических игр. Это касается игры Сильвер Чеканка, в котором игроки по очереди задают положительное целое число, которое не может быть выражено как сумму ранее указанных значений, при этом игрок проигрывает, когда его заставляют указать число 1. Существует алгоритм (приведенный в книге в виде блок-схемы) для определения того, является ли данный первый ход выигрышным или проигрышным: если это простое число больше трех, или один из конечного набора 3-гладкие числа, то первый ход является выигрышным, в противном случае - проигрышным. Однако конечный набор неизвестен.

В теории графов

Доказательства неконструктивного алгоритма для задач в теория графов изучались с 1988 г. Майкл Феллоуз и Майкл Лэнгстон.[1]

Распространенный вопрос в теории графов - обладает ли определенный входной граф определенным свойством. Например:

Вход: график грамм.
Вопрос: Может грамм быть вложенным в 3-мерное пространство, так что никакие два непересекающихся цикла грамм топологически связаны (как звенья цепи)?

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

Однако существует неконструктивное доказательство, которое показывает, что сцепленность разрешима за полиномиальное время. Доказательство опирается на следующие факты:

  • Множество графиков, для которых ответ положительный, закрывается несовершеннолетние. То есть, если граф G может быть вложен без ссылок в трехмерное пространство, то каждый минор графа G также может быть вложен без ссылок.
  • Для каждых двух графиков грамм и ЧАС, можно за полиномиальное время определить, ЧАС является несовершеннолетним из грамм.
  • К Теорема Робертсона – Сеймура, любой набор конечных графов содержит только конечное число минорно-минимальных элементов. В частности, набор примеров «да» имеет конечное число минорно-минимальных элементов.

Учитывая входной граф грамм, следующий "алгоритм" решает указанную выше проблему:

Для каждого минорно-минимального элемента ЧАС:
Если ЧАС является несовершеннолетним из грамм затем ответьте «да».
верните «нет».

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

Есть еще много подобных задач, разрешимость которых доказывается аналогичным образом. В некоторых случаях знание того, что проблема может быть доказана за полиномиальное время, побудило исследователей искать и находить реальный алгоритм полиномиального времени, который решает проблему совершенно другим способом. Это показывает, что неконструктивные доказательства могут иметь конструктивные результаты.[1]

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

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

Подсчет алгоритмов

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

В качестве примера рассмотрим следующую проблему.[3]

Я выбираю вектор v состоит из п элементы, которые являются целыми числами от 0 до определенной константы d.

Ты должен угадать v спрашивая сумма запросов, которые представляют собой запросы вида: "какова сумма элементов с индексами я и j? ". Запрос суммы может относиться к любому количеству индексов от 1 до п.

Сколько запросов вам нужно? Очевидно, п запросов всегда достаточно, потому что вы можете использовать п запросы, запрашивающие "сумму" одного элемента. Но когда d достаточно мала, можно лучше. Общая идея такова.

Каждый запрос может быть представлен в видеп вектор, все элементы которого входят в набор {0,1}. Ответ на запрос - это просто скалярное произведение вектора запроса на v. Каждый набор k запросы могут быть представлены k-к-п матрица над {0,1}; набор ответов - произведение матрицы на v.

Матрица M "хорошо", если позволяет однозначно идентифицировать v. Это означает, что для каждого вектора v, продукт M v уникален. Матрица M "плохо", если есть два разных вектора, v и ты, так что M v = М ты.

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

Это доказательство неконструктивно по двум причинам: неизвестно, как найти хорошую матрицу; и даже если предоставлена ​​хорошая матрица, неизвестно, как эффективно восстановить вектор из ответов на запросы.

Есть еще много подобных проблем, решение которых может быть доказано аналогичным образом.[3]

Дополнительные примеры

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

  1. ^ а б Товарищи, M. R .; Лэнгстон, М.А. (1988). «Неконструктивные инструменты для доказательства разрешимости полиномиального времени». Журнал ACM. 35 (3): 727. Дои:10.1145/44483.44491. S2CID  16587284.
  2. ^ Браун, Д. Дж .; Товарищи, M. R .; Лэнгстон, М.А. (2007). «Самосводимость за полиномиальное время: теоретические обоснования и практические результаты *». Международный журнал компьютерной математики. 31 (1–2): 1–9. Дои:10.1080/00207168908803783.
  3. ^ а б Гребинский, В .; Кучеров, Г. (2000). «Оптимальная реконструкция графов по аддитивной модели» (PDF). Алгоритмика. 28: 104–124. Дои:10.1007 / s004530010033. S2CID  33176053.
  4. ^ Киммел, С. (2013). «Квантовый противник (верхняя) граница». Чикагский журнал теоретической информатики. 19: 1–14. arXiv:1101.0797. Дои:10.4086 / cjtcs.2013.004. S2CID  119264518.

Кредиты

Ссылки на этой странице были собраны из следующих Обмен стеком потоки:

Смотрите также