[已解决]关于P类，NP，NPC，NPhard问题

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

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

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

求大佬解释

最佳答案

lovedai

2020-11-18 09:50:44

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

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

这个概念我也有点混乱

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了，在解不出来只能验证的时候再考虑，个人看法

好的谢谢！

账号		自动登录	找回密码
密码			立即注册