Как доказать, что SAT является NP-полным?

Question

Как это так, как вы доказываете, что SAT является NP-полным?

Я знаю, что это значит под NP-полным, поэтому мне не нужно объяснение по этому поводу.

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

Answer 1

Я полагаю, что 3-SAT первоначально уменьшился от более общей удовлетворенности в статье Карпа, в которой обрисовано 21 NP-полные проблемы.

Википедия имеет описание как показать, что удовлетворенность является NP-полным, результатом, который известен как Кук-Левин Теорема. Анкет Идея этого доказательства состоит в том, чтобы показать, что любая полиномиальная недерминированная машина Тьюринга может быть смоделирована как логическое выражение с полиномиальным размером. Логическое выражение имеет термины для представления достоверного пространства конфигурации машины Тьюринга: где находится головка ленты, каково текущее состояние, какие символы записываются на ленте и какие переходы действительны в каждой позиции. Поскольку NTM остановится в полиномиальном времени, пространство конфигурации ограничено, и мы можем сделать (большое) полиномиальное выражение для его представления.