Почему все NP-полные проблемы можно свести к 3-SAT?

Question

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

Начнем с того, что все NP-полные задачи сводятся к 3SAT. 3-SAT?

Надеюсь на ваш ответ: -)

Answer 1

По определению, NP -полная проблема X обладает тем свойством, что каждая задача Y ∈ NP сводится к X. (Это то, что NP -твердость означает.) Аналогично, по определению каждая NP -полная проблема находится в NP . Если сложить эти два значения вместе, каждая NP -полная проблема сводится к любой другой, поэтому все NP -полные проблемы сводятся к 3SAT.