В поисках литературного источника для следующей идеи

12

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

Идея состоит в том, чтобы построить машину Тьюринга M со свойством, что если P = NP, то M будет решать 3-SAT за полиномиальное время. (Выбор 3-SAT является произвольным. Это может быть действительно любая проблема в NP).

Просто чтобы быть ясно, это не утверждение, что P = NP. На самом деле я верю в обратное. Я просто утверждаю, что если P = NP, то M обеспечит решение за полиномиальное время. Если вы ищете эффективное решение, я должен предупредить, что это далеко не эффективно.

M строится следующим образом: сначала примите каноническое кодирование для всех машин Тьюринга и примените нумерацию к этим машинам. Итак, существует машина Тьюринга № 1, № 2 и т. Д. Идея универсальной машины Тьюринга, которая может считывать формат для предоставленной машины и затем моделировать работу этой машины на отдельном входе, достаточно известна. M будет использовать универсальную машину Тьюринга для постройки и моделирования каждой машины Тьюринга по очереди.

Сначала он имитирует работу машины Тьюринга 1 за один шаг.
Затем он просматривает выходные данные машины Тьюринга 1.
Он имитирует работу машины Тьюринга 1 в течение двух этапов и просматривает выходные данные, затем переходит к моделированию машины Тьюринга 2 в течение 2 шагов. Это продолжается и повторяется таким образом, в свою очередь, запустив машину Тьюринга 1 для k шагов, затем 2 для k шагов ... затем, в конце концов, машину k для k шагов.

После каждого прогона симуляции он проверяет результаты прогона. Если выходные данные являются назначением переменных, удовлетворяющих экземпляру задачи 3-SAT, M останавливается в состоянии принятия. Если, с другой стороны, выходные данные являются строкой доказательства на некотором проверяемом языке доказательств с доказанным результатом, что экземпляр проблемы не выполним, M останавливается в состоянии отклонения. (Для языка доказательств мы могли бы, например, использовать аксиомы Пеано с логикой второго порядка и основные логические аксиомы в гильбертовом стиле. Я оставляю читателю в качестве упражнения понять, что если P = NP, язык доказательства существует и может быть проверен за полиномиальное время).

Здесь я буду утверждать, что M решит 3-SAT за полиномиальное время тогда и только тогда, когда P = NP. В конце концов, алгоритм найдет какую-то волшебную машину Тьюринга с номером K, которая, как оказалось, является эффективным средством решения проблемы 3-SAT и способна предоставить доказательства ее результатов как для успеха, так и для неудачи. K в конечном итоге будет смоделирован, выполняя шаги poly (strlen (input)) для некоторого полинома. Многочлен для M примерно равен квадрату многочлена для k в наибольшем множителе, но с некоторыми ужасными константами в многочлене.

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

Билл Провинция
источник

Ответы:

16

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

φP=NPφ

Комментарий 2: Как Ярослав Блазиок указал в другом ответе, этот алгоритм не определяет Sat только при условии P = NP.

Матеус де Оливейра Оливейра
источник
Я только что нашел ссылку на Википедию, и действительно, в ней упоминается Левин, но без цитирования. Возможно, это просто стало фольклором, но никогда не использовалось в опубликованной литературе. В любом случае, это полезно. Благодарю.
Билл Провинция
Добро пожаловать. Я нашел домашнюю страницу с несколькими ссылками на эту тему. Я отредактировал ответ, чтобы включить его.
Матеус де Оливейра Оливейра
6

Идея диагонального запуска всех возможных машин Тьюринга ранее использовалась Леонидом Левиным в так называемом универсальном поиске Левинса. К сожалению, и вопреки чрезвычайно распространенному заблуждению, для того, что я знаю, вариации универсального поиска Левина НЕ способны обеспечить явный алгоритм решения SAT (проблема решения) за полиномиальное время, учитывая только предположение, что P = NP - и ни один ваш алгоритм не делает ,

Предостережение из предложенных рассуждений (как и очень часто) заключается в «простом упражнении, оставленном читателю» - я сам не смог доказать упражнение и не верю, что его утверждение верно, а именно:

Предполагая, что P = NP, существуют полиномиальные размеры ZFC, доказывающие неудовлетворительность данной булевой формулы.

Более того: я не вижу, как доказать существование полиномиально короткого ZFC, доказывающего неудовлетворенность при (более сильном) предположении, что «P = NP доказуемо в ZFC». Это становится легким, однако, при еще более сильном предположении, а именно:

(*) Существует машина М, работающая за полиномиальное время, которая доказуемо решает SAT.

И это, я полагаю, правильное предположение, согласно которому ваш алгоритм решает SAT за полиномиальное время. Выше «доказуемо решает SAT» я имею в виду: существует машина M и доказательство ZFC, что M решает SAT.

Обратите внимание, что это предположение все еще немного слабее, чем следующее: (**) Существует машина M, которая доказуемо работает за полиномиальное время и доказуемо решает SAT.

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

Правда, однако, что в предположении P = NP существует некоторая полиномиально проверяемая система доказательств с короткими доказательствами неудовлетворенности заданной формулой. К сожалению, мы не знаем ни системы проверки правдоподобия, ни проверяющей стороны, и это не помогает в этой настройке.

f1(x)

Обратите внимание, что эта схема применяется, например, к проблеме ФАКТОРИНГА; здесь f - просто умножение (определено только для факторов, отличных от \ pm 1), а B - проверка первичности. Следовательно, универсальный поиск Левинса будет (с точностью до постоянного множителя) оптимальным алгоритмом ФАКТОРИНГА. Учитывая, что оптимальный алгоритм медленнее, чем известный алгоритм проверки первичности - в другом случае проверка первичности становится доминирующей.

NPcoNP

Ярослав Бласиок
источник
1
Если P = NP, то co-NP = co-P = P = NP. Итак, UNSATISFIABILITY в NP, как и свидетели полиномиального размера - вам не нужно вызывать машину Тьюринга. Разве вы не можете превратить этого свидетеля в доказательство ZFC, что формула неудовлетворительная? Я не разбираюсь в механике доказательства ZFC, но интуиция, которую я получил из разных мест, заключается в том, что, если вы не имеете дело с "странными вещами", ZFC соответствует всем вещам, которые вы, как вы думали, вы могли доказать в любом случае, до того, как Вы слышали о теории множеств. Конечные объекты, такие как булева формула и полиномиальное свидетельство ее неудовлетворенности, вряд ли будут странными.
Дэвид Ричерби
Да, если P = NP, то UNSAT находится в NP, и у него есть свидетельство полиномиального размера. А именно: свидетель нулевого размера, вся работа выполняется проверяющим, верно? Я имею в виду только одну идею, как преобразовать этого свидетеля нулевого размера в доказательство ZFC неудовлетворительности: дать ZFC доказательство того, что моя машина действительно решает проблему UNSAT, а затем показать запуск этой машины по формуле - это было бы достоверным доказательством, и это соответствует тому факту, что алгоритм, предложенный OP, работает в (*). Но что, если бы была какая-то хитрая машина, которая просто могла решить SAT, но этот факт недоказуем? Не то, чтобы я поверил, что это так
Ярослав Бласиок
1
Неправильное представление, к которому я обращаюсь, гласит: «Если P = NP, то Универсальный поиск Левинса дает алгоритм за полиномиальное время, решающий NP-полную задачу», или, как иногда говорят: «Невозможно иметь только неконструктивное доказательство P = NP, потому что алгоритма Левина ". И те, и другие являются ложными - формулировка Википедии представляет метод, который останавливается в polytime на экземплярах YES SUBSET SUM, но не останавливается вообще на NO-экземплярах - это не алгоритм, определяющий сумму подмножеств в polytime. Формулировка OP лучше подходит для этой цели, но требует более сильного допущения, чем P = NP, чтобы определить SAT в политизме.
Ярослав Бласиок
1
NPcoNP
1
Теперь способ справиться с этим, поскольку вы не знаете явно верификатора для проблемы unSAT, состоит в том, чтобы попытаться найти краткое доказательство в некоторой формальной логике, которую мы уже знаем и можем проверить (пусть это будут аксиомы ZFC или Пеано - мы более вероятно, чтобы найти краткое доказательство в первом, хотя), что этот случай является неудовлетворительным. Но если кто-то хочет доказать, что в этой формальной логике есть такое короткое доказательство, нужно более сильное предположение, чем P = NP.
Ярослав Бласиок