确定性图灵机与非确定性图灵机，P、NP、NP-Completeness、NP-Hard 等概念简记。

确定性图灵机

TM (Turing machine) 与 NTM (nondeterministic Turing machine)

图灵机（又称确定性图灵机），是一种「数学计算模型」。它描述了一种「抽象机」，可以根据规则表，在磁带上操作、维护相关符号、状态。虽然是个简单的模型，但它可以实现任何计算机算法。

非确定性图灵机，和确定性图灵机相比，是指给定符号和状态的情况下，NTM 可以做多个操作（或下一步操作不由符号和状态确定）。举个忙碌海狸（Busy Beaver）的例子是：当磁带的 symbol 为 1，且当前状态为 B 的时候，可以允许 NTM 有多个不同的分支逻辑。从 NPC 的定义来看，非确定性是一种数学上形式化暴力搜索算法。

“nondeterministic” refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm.

image

P

P 问题：可以由一个确定型图灵机在多项式表达的时间内解决的问题。 表示 Polynomial（多项式），即在「多项式」时间内，可被「有效」解决的问题。

  • 可在定性图灵机中，在多项式时间内解决的问题（即可以被有效解决的问题）

It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

NP

NP (nondeterministic polynomial time) 表示 Nondeterministic Polynomial。有两种情况：

  • 可在确定性图灵机中，在多项式时间内验证的问题（即可以被有效验证的问题）
  • 可在非确定性图灵机中，在多项式时间内解决的问题（即可以被非确定性地解决）

NP is the set of decision problems for which the problem instances, where the answer is “yes”, have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.[2]

P 与 NP

P 与 NP 问题的关系，目前还是计算机领域的未解决问题。

NPC

NPC 是非确定性多项式时间完全的简写。

  • 非确定性：指非确定性图灵机，也指需要暴力搜索的算法
  • 多项式时间：指能有效解决、或有效验证的。具体查看上述 NP 的理解。
  • 完全：是指能将问题简化为子问题，且能在多项式时间内解决。（如动态规划的问题）
    • 如果不能简化或解决，那么就是 NP-Hard 问题。

The name “NP-complete” is short for “nondeterministic polynomial-time complete”. In this name, “nondeterministic” refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered “quick” for a deterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform the whole search. “Complete” refers to the property of being able to simulate everything in the same complexity class.

NPC 与 NP-Hard 的关系

典型的 NPC 问题

Reference

https://en.wikipedia.org/wiki/NP_(complexity) https://en.wikipedia.org/wiki/Nondeterministic_Turing_machine https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science https://dona-sarkar009.medium.com/p-np-and-npc-67111a1d860e