P和NP那些事
这篇讲的是计算机科学中P、NP、NP完全（NPC）与NP难（NP-hard）这几个核心概念。很多人误以为NP就是“非P”，文章一开始就澄清了这一点：NP（非确定性多项式时间）问题指的是那些“能在多项式时间内被验证解”的问题，而P（多项式时间）问题自然属于NP。 作者用一个生动的比喻解释了NP的核心：非确定型图灵机可以“猜”出一个解（比如哈密顿路径），然后快速验证其正确性。接着，文章引入了“规约”这一关键工具，并指出Cook发现了所有NP问题都可规约到SAT问题，由此引出NP完全问题——NP中最困难的一类，它需同时满足“是NP问题”且“所有NP问题都可规约到它”这两个条件。 文章还以SAT、2-SAT（P）与3-SAT（NPC）为例，具体说明了概念间的差异，并列举了旅行商问题等经典NPC问题。最后，作者提及了对P≠NP证明尝试的看法，认为这可能需要现有理论体系之外的突破。全文从澄清误解入手，层层拆解概念间的逻辑关系，为理解这个理论计算机科学的核心难题提供了清晰的脉络。
