20211217-NP问题

发表于 更新于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

什么是P问题、NP问题、NPC问题、NP-hard问题？

1. 基本概念

  • 通常所谓的NP问题，实际上就是：证明或推翻P=NP；
  • NPC：只有搜才行；
  • 时间复杂度：并非表示一个程序解决时间需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长多快；
  • 不可解问题（Undecidable Decision Problem）：例如The Halting Problem；
  • P问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，该问题则属于P问题。我们通常见到的信息奥赛的题目都是P问题，因为一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法；

  • NP问题：找到一个比100小的解（全部找出来不容易，但是验证其中一个解是容易的）；

    • 定义1：可以在多项式的时间里验证一个解的问题（并不是非P问题）；
    • 定义2：可以在多项式的时间里猜出一个解的问题；
  • 通常只有NP问题才可能找到多项式的算法，我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。
  • 目前人们普遍认为P=NP问题不成立，即存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P!=NP的原因在于：NPC问题的存在，即NP-完全问题；

  • 约化（Reducibility）：Hamilton回路问题可以约化为TSP问题；

    • 定义1：一个问题A可以约化为问题B，即可以用问题B的解法解决问题A，或称”问题A可以变成问题B“；
    • 定义2：可以找到一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B 的输入，使两个程序的输出相同；
    • 约化具有传递性；

  • NPC问题：所有的NP问题都可以约化成它；

    • 定义：
      • 条件1：该问题是NP问题；
      • 条件2：所有的NP问题都可以约化成它；
    • 证明：
      • 首先证明它至少是一个NP问题；
      • 证明其中一个已知的NPC问题能约化到它；
    • 逻辑电路问题属于NPC问题，因为其显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证明造成不可逾越的困难）。证明过程相当复杂，大致意思是：任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出，因此对于一个NP问题而言，问题转化为了求出满足结果为True的一个输入（即一个可行解）；
    • 已被证明是NPC的问题：Hamilton回路、TSP问题；
  • NP-hard问题：满足NPC问题的第二条，但是不一定要满足第一条。因此NP-hard问题有可能仍然无法得到多项式级别的算法。

2. 推论

  • 所有的P类问题都是NP问题：能多项式地解决一个问题，必然能多项式地验证一个问题的解；
  • 所有的NP问题都能约化成NPC问题，因此只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决，即NP=P；

3. 0-1背包问题是NP完全问题