如何将 3COLOR 降低为 3SAT？
我们知道3SAT ≤p 3COLOR（即3SAT 是多项式时间可简化为3COLOR）。 谁能简短地论证一下为什么 3COLOR ≤p 3SAT？ 并给出实际的库克减少，表明 3COLOR ≤p 3SAT 请。
We know that 3SAT ≤p 3COLOR(i.e. 3SAT is polynomial time reducible to 3COLOR).
Can anyone give a short argument why 3COLOR ≤p 3SAT?
And give an actual Cook reduction showing that 3COLOR ≤p 3SAT Please.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
简短的答案是：由于 3SAT 是 NP 完全的，因此 NP 中的任何问题都可以简化为
解决 3SAT 的一个实例（或表明它不可满足）。因此3COLOR≤p 3SAT。
对于 3COLOR 到 SAT 的 pt 还原的构造，您可以参见 中的第 2 节
以下文档（该主题与您的问题无关）：
http:// Research.microsoft.com/apps/pubs/default.aspx?id=66816
the short answer is: since 3SAT is NP-complete, any problem in NP can be p.t. reduced to
solving an instance of 3SAT (or showing it is not satisfiable). Hence 3COLOR <=p 3SAT.
For a construction of p.t. reduction of 3COLOR to SAT, you may see section 2 in the
following document (the topic is not related to your question):
http://research.microsoft.com/apps/pubs/default.aspx?id=66816