如何将 3COLOR 降低为 3SAT？
我们知道3SAT ≤p 3COLOR（即3SAT 是多项式时间可简化为3COLOR）。 谁能简短地论证一下为什么 3COLOR ≤p 3SAT？ 并给出实际的库克减少，表明 3COLOR …
一般为 NP 困难但在平面图中具有多项式时间解的问题列表？
我遇到了很多可以表述为图形问题的问题。 它通常是 NP 困难的，但有时可以证明该图是平面的。 因此，我对学习这些问题和算法很感兴趣。 据我所知： 平…
NP 中最长的可能非简单路径吗？
我知道下面的问题是NP-HARD中的：给定一个简单的图G=(V,E)，V中的两个顶点v，v'，一个整数B和一个非负长度函数len：E-> Z+，是否有一条从 v 到 v' 且…
证明问题的 NP 完备性
我们给定一个集合 A = {a1,a2,...,an} 给定 A 的子集 B1，B2，...，Bm。如果名为 H 的 A 子集与所有给定的 B 都有交集，我们将 H 称为“覆盖子集”。…
