Достаточно ли сокращения для доказательства NP-завершения или мне нужно преобразование? - PullRequest
Новая
       19

Достаточно ли сокращения для доказательства NP-завершения или мне нужно преобразование?

1 голос
/ 13 сентября 2011

Если у меня есть решение задачи A, и я хочу показать, что она NP-полная.Достаточно ли доказать, что другая NP-полная задача полиномиально сводится к A, или я должен показать, что другая NP-полная задача полиномиально преобразуется в A?

То есть, могу ли я показать, что 

procedure solve_SAT
...
call solve_A
call solve_A
call solve_A
...
end

или я ограничен только одним использованием solve_A, как показано 

procedure solve_SAT
input  = ...
result = call solve_A(input)
return result
end

Я считаю, что некоторые источники говорятпервое, в то время как другие источники говорят о втором, и это меня немного смущает.

Ответы [ 3 ]

2 голосов
/ 28 января 2012

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

Итак, предположим, что вы хотите показать, что 3-SAT является NP-Complete, тогда вы можете показать уменьшение проблемы SAT.

Здесь важно отметить, что сокращение должно быть многократным. Не имеет значения, вызываете ли вы метод решайте несколько раз. Вы можете вызывать solve_A () несколько раз, если выполняете полиномиальное количество вызовов функции solve_A ().

Почему это работает? Вы можете доказать это противоречием. Предположим, у вас был алгоритм поли-времени для 3SAT. Тогда вы можете решить SAT также в поли-времени. Поскольку полиномиальное количество обращений к полиномиальной функции все еще является полиномиальным. Таким образом, если P = NP, это будет означать, что SAT также может быть решена за полиномиальное время с использованием недавно открытого алгоритма поли-времени для 3SAT. Но мы знаем, что SAT является NP-Complete, следовательно, 3SAT также должен быть NP-Complete.

Короче говоря, чтобы показать NP-полноту, требуются две вещи.

Наличие сертификата. Сокращение от существующей проблемы NP-Complete.

1 голос
/ 13 сентября 2011

Если ваша процедура для solve_SAT использует только постоянное количество вызовов для solve_A, то алгоритм полиномиального времени для A подразумевает алгоритм полиномиального времени для SAT.Это не соответствует точному определению SAT, но это подразумевает, что не существует никакого алгоритма полиномиального времени для A, если P = NP.

0 голосов
/ 27 января 2012

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

Ваш другой пример, где вы можете вызвать solve_A полиномиальное число раз, соответствующее тьюрингу или кукуснижение.Существование сокращения Тьюринга от NP-полной задачи к вашей проблеме является доказательством NP-сложности вашей задачи, которая, как считается, отличается от NP-полноты.

...