SATがNPコンプリートであることをどのように証明しますか？

Question

現状では、SATがNPが完全であることをどのように証明しますか？

私はそれがNPコンプリートの意味を知っているので、それについて説明する必要はありません。

私が知りたいのは、SATなどの1つの問題が、ハミルトニアンの問題などの他の問題を減らすことに頼ることなく、NP不完全であることをどのように知っているのかということです。

Answer 1

3-SATはもともと、概説したKarpの論文のより一般的な満足度から減少したと思います 21 NP不完全な問題.

ウィキペディアには説明があります 満足度がNPコンプリートであることを示す方法の結果は、 クックレビン定理. 。この証拠の考え方は、多項式時間の非決定的チューリングマシンが多項式サイズのブール表現としてモデル化できることを示すことです。ブール式には、チューリングマシンの有効な構成空間を表す用語があります。テープヘッドがどこにあるか、現在の状態とは何か、テープに記号が書かれているか、すべての位置でどの遷移が有効ですか。 NTMは多項式時間で停止するため、構成空間が境界に縛られ、それを表すために（大きな）多項式発現を作成できます。