【研一周小结】第六周个人学习总结_三色问题是npc吗-CSDN博客

网友收藏2023-10-13 09:40

链接地址：https://blog.csdn.net/Hide_in_Code/article/details/115447389
链接标题：【研一周小结】第六周个人学习总结_三色问题是npc吗-CSDN博客
所属网站：blog.csdn.net
被收藏次数：279

第六周学习总结 21-04-05SIST Yippee1 算法设计与分析本周内容依然是讲述NP系列问题，但围绕的主题是证明各色问题是NPC问题：证明哈密顿回路、有向哈密顿回路是NPC问题——构建符合3-SAT的图结构，归约成3-SAT问题来证明；证明旅行商问题TSP是HPC问题——先证明“至少k长度的简单路径”是HPC问题，然后把TSP归约成后者来证；3-Dimensional Matching（三元组匹配）问题，证明其是NPC问题。三色图上色问题，证明其是NPC问题。”数字子集和能否_三色问题是npc吗

本文地址：https://tebull.com/detail/95590.html

标签：三色问题是npc吗