纵戈 发表于 2020-11-18 09:50:43

关于P类，NP，NPC，NPhard问题

假设： 我有两张无向图， 顶点数一样， 但路径（边）不同。
问：二图是否相同？

求助：请问上述问题属于P类问题，还是NP, NPC, NP-hard?

求大佬解释{:10_254:}

lovedai 发表于 2020-11-18 09:50:44

P类，必然有多项式时间内解决的办法

纵戈 发表于 2020-11-18 10:09:40

追加解释：相同就是完全一样，不是同构的意思

纵戈 发表于 2020-11-18 11:14:08

lovedai 发表于 2020-11-18 11:00
P类，必然有多项式时间内解决的办法

请问为什么不是NPC{:10_257:}
这个概念我也有点混乱

lovedai 发表于 2020-11-18 11:59:25

纵戈 发表于 2020-11-18 11:14
请问为什么不是NPC
这个概念我也有点混乱

确定能解出来就不考虑npc了，在解不出来只能验证的时候再考虑，个人看法

纵戈 发表于 2020-11-18 18:16:03

lovedai 发表于 2020-11-18 11:59
确定能解出来就不考虑npc了，在解不出来只能验证的时候再考虑，个人看法

好的谢谢！
页: [1]
查看完整版本: 关于P类，NP，NPC，NPhard问题