3SAT≤p3COLOR（つまり、3SATは3COLORに還元可能な多項式時間）であることがわかっています。なぜ3COLOR≤p3SATなのか、誰かが短い議論をすることができますか？そして、3COLOR≤p3SATであることを示す実際のクックリダクションを与えてください。
3933 次
1 に答える
2
簡単な答えは次のとおりです。3SATはNP完全であるため、NPの問題は、3SATのインスタンスを解決する（または満足できないことを示す）ことに減らすことができます。したがって、3COLOR <=p3SATです。
3COLORからSATへのpt削減の構築については、次のドキュメントのセクション2を参照してください（トピックは質問とは関係ありません）。
http://research.microsoft.com/apps/pubs/default.aspx?id=66816
于 2011-10-25T09:04:10.627 に答える