第七章np问题选讲内容摘要：
那么 3CNF亦可以。 也就是说：最大团不会比 3CNF容易。 •已知最大团问题是一个 NPC问题，试证明顶点覆盖问题也是 NPC问题 –首先易证顶点覆盖是一个 NP问题。 –为最大团的图 G构造一个图 G’ –然后欲证图 G有一个大小为 k的团当且仅当图G’ 有一个大小为 |V|k的顶点覆盖 –多项式规约说明：顶点覆盖不会比最大团问题容易。 –如果最大团是 NPC，顶点覆盖也是 NPC。 CircuitSAT SAT 3CNFSAT Clique VertexCover SubsetSum HamCycle TSP GraphColoring SetCover Partition BinPacking ParallelScheduling Knapsack StripPacking •以往的转化 –欲解决问题 A，将其转化为较简单的问题 B，。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。