Сведение задачи целочисленной факторизации к задаче NP-Complete

17

Я изо всех сил пытаюсь понять отношения между NP-Intermediate и NP-Complete. Я знаю, что если P! = NP, основанный на теореме Ладнера, существует класс языков в NP, но не в P или в NP-Complete. Каждая проблема в NP может быть сведена к проблеме NP-Complete, однако я не видел примеров того, как свести подозреваемую проблему NPI (например, целочисленную факторизацию) к проблеме NP-Complete. Кто-нибудь знает какой-либо пример этого или другого сокращения NPI-> NPC?

np-complete reductions factoring Натан Джордан
источник
4
По определению NP-полноты любая проблема в NP может быть сведена к любой NP-полной задаче. В частности, теорема Кука показывает, что SAT является NP-полной, и поэтому дает вам «явное» такое сокращение.
Юваль Фильмус
1
@YuvalFilmus Я понимаю, что существует формализация того, что такой метод существует, однако я искал более конкретный алгоритмический подход, подобный, скажем, сведению задачи о гамильтоновом цикле к проблеме коммивояжера. При этом вы можете установить все веса ребер на 1 и запустить TSP на графике и проверить, больше ли пройденное расстояние, чем | E |. Полагаю, что-то подобное.
Натан Джордан

Ответы:

11

Например, существует классическое сокращение факторинга до SAT, который также является источником предполагаемых «жестких» экземпляров SAT. В основном каждый использует идеи EE для двоичного умножения, закодированного в схеме SAT. Думайте о двоичном умножении как о добавлении серии сдвинутых влево мультипликаторов, каждый из которых «маскируется» (ANDed) битами множителя. Дополнения могут выполняться схемой двоичного сложения, которая представляет собой последовательность полных сумматоров.

Талантливый студент может построить этот алгоритм. Я не знаю, где это было впервые предложено или реализовано в литературе. Мне было бы интересно услышать любые ссылки.

См., Например, « Удовлетворение этим: попытка решения первичной факторизации с использованием решателей удовлетворенности» Штефана Шенмеккера и Анны Кавендер, в которой это подробно изложено. Кроме того, задача DIMACS SAT, начавшаяся в конце 90-х годов, имела факторинговые примеры, которые были сгенерированы некоторыми исследователями, но, возможно, алгоритм не был написан отдельно в статье в ту эпоху.

ВЗН
источник
1
К сожалению, ссылка на статью теперь запрещена 403
vzn
2
Что касается вашего второго абзаца: теорема Кука показывает, что любая проблема в NP может быть сведена к SAT.
Юваль Фильмус
1
верно, доказательство Кука является общетеоретическим доказательством существования, и существует более прямые / специализированные преобразования / алгоритмы, часто создаваемые между NP-полными задачами (обычно с лучшими «накладными расходами»). имел в виду последнее.
vzn
11

Просто чтобы быть абсолютно ясным, Integer Factorization, как известно, не является NP-промежуточным звеном, просто предполагается, что он основан на отсутствии либо NP-полноты, либо алгоритма за полиномиальное время (несмотря на большую работу, вложенную в оба). Я не знаю ни одной естественной проблемы (т.е. не построенной Ладнером для доказательства), которая определенно является NP-промежуточной, если P и NP разные.

Хорошо, после этого отказа от ответственности граф Изоморфизм является еще одним вероятным кандидатом на естественную NP-промежуточную проблему. Существует простое сокращение полиномиального времени от него до изоморфизма подграфа - просто оставьте графики одинаковыми! Изоморфизм графов - это частный случай изоморфизма подграфов, когда оба графа имеют одинаковый размер. Последним штрихом является то , что подграф Изоморфизм является NP-полной.

Кроме того, всегда есть не столь информативное сокращение, обещанное теоремой Кука-Левина , мы знаем, что любая NP-промежуточная задача имеет некоторую недетерминированную машину Тьюринга за полиномиальное время, которая ее решает, и мы можем преобразовать ее в экземпляр SAT (просто нужно построить ТМ!).

Люк Мэтисон
источник