P，NP，NPC，NPH

-- TOC --

P （Polynomial）
NP（Non-deterministic Polynomial）
P equals NP?
NPC
NPH
Decision Problem

P （Polynomial）

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.

NP（Non-deterministic Polynomial）

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 a Deterministic 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 equals NP?

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

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

NPC

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.

NPH

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

Decision Problem

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

-- EOF --

-- MORE --