算法-对时间复杂度的汇总

P,NP,P-SPACE

P

Polynomial time 多项式时间内($n^c$)有正确解。n是输入规模，c是常数。ep：是否是质数，两点之间最短距离。

NP

Non-deterministic Polynomial time 能在多项式时间内验证是否有正确答案。返回True，False。NP问题都有“short witnesses”使其能快速验证答案。

PH

Polynomial Hierarchy(多层式分级) 如果一个问题开始是NP，但随后会增加额外的复杂性，该问题就是PH。ep: 给定X，是否存在一个Y，使得对于所有的Z。