-- TOC --

- The class
**P**consists of those problems that are solvable in polynomial time. More specifically, they are problems that can be solved in \(O(N^k)\) time for some constant k, where N is the size of the input to the problem.

- The class
**NP**(Non-deterministic Polynomial) consists of those problems that can be solved in polynomail time on a NDTM.

**NDTM（Non-Deterministic Turing Machine）**

A Non-Deterministic Turing Machine (NDTM) is a

`theoretical model of computation`

that, unlike aDeterministic Turing machine (DTM), can explore multiple possibilities simultaneously. It can follow multiple paths simultaneously, potentially allowing for more efficient processing of certain problems. An NDTM has the capability to`guess`

the correct next action at each step, rather than relying on a deterministic transition function. This ability to explore multiple paths at once allows for the possibility of solving problems faster than deterministic Turing Machines, particularly for problems with many possible solutions or paths.

NDTM is just similar, but not the same with quantum computing!

**判断NP问题的方法**

猜一个解，判断是否可以在polynomial时间内可验证。

- \(P\subseteq NP\), but whether \(P=NP\) or not?

这是计算机理论中，最重要的一个open question！很多人认为NP不等于NP，但是给不出证明。也没有人能够给出一个Polynomail的算法来解决某个NP问题。

**NPC**stands for NP-Complete, which belongs to NP and any NP problem can be reduced to it. If any NPC problem can be solved in polynomial time, then every problem in NP has a polynomial-time algorithm. One should be capable for identifying NPC problem and avoid it by approximation algorithms.

**NP-Hard**might not be a NP, but any NP can reduce to it.

本文链接：https://cs.pynote.net/ag/202404241/

-- EOF --

**-- MORE --**