[Algorithm] NP/NPC/NP-Hard

我们上课用的ppt 来自 Waterloo U. 作业来自 Berkeley。 非常难,但也很有趣。

既然 ppt 来自滑铁卢大学,那一定带有吹加拿大人的部分,比如这个提出21 个 NPC 问题的 Karp。

关于NP & NPC & NP-Hard 问题。

可以用用一个数轴来解决。

虽然不是很精确,但来说没问题。

现在来讲解一下npc。

在 MIT 的公开课 6.046 上 用了这样一个思维导图。

$(x_{1}\wedge x_{2}\wedge \not x_{3})v(x_{4}\wedge x_{5}\wedge x_{6})$