• Classify Problems
  • polynomial-times and those that cannot

    • Reduction: PX polynomial reduces to PY if arbitrary instances of problems X can be solved using

      1. Polynomial number of standard computational steps
      2. Polynomial number of calls to oracle that solves PY

      $$ X\le_p Y $$

      PY 可多项式求解，X可多项式求解；X不可多项式求解，Y亦不可。

      tips： X→ Y 输入规模至多多项式增大（condition 1）

      • Establish intractability
      • Establish equivalence

      ---

      • reduction by encoding with gadgets

• 最大独立集 vs 最小点覆盖

  vs vertex cover

• 点覆盖 vs 集合覆盖

• 布尔电路满足问题 Satisfiability (SAT→3-SAT)vs 独立集 （有解、无解两种情况）

• PRIME https://en.wikipedia.org/wiki/AKS_primality_test

判断问题

P:存在poly-time 的判断问题

1. MULTIPLE 因子判断
2. RELPRIME： relatively prime互质|辗转相除法
3. PRIMES:AKS
4. EDIT-DISTANCE
5. LSOLVE 求解线性方程组

NP 存在 poly-time验证算法certifier的问题（存在多项式非确定性算法）|nondeterministic polynomial-time 非确定性多项式时间算法

EXP 存在指数时间exponential-time 算法的判断问题集合

NP-complete $\forall X\in \text{NP}\le _pY\in \text{NP}$

1. circuit satisfiability| CIRCUIT-SAT (cook 1971)

<aside>

step 1 $Y\in\text{NP}$

step 2 choose an np-complete problem X

step 3 Prove that $X\le _p Y$

所有的NPC都可以相互规约

</aside>

1. -》 3-SAT-》独立集-》点覆盖-》集合覆盖
2. 子集和→ 调度
3. 三色涂→ PLANAR 3-COLOR→ TSP
4. → DIR-HAM-CYCLE→HAM-CYCLE→TSP

1. graph isomorphism 图同构
2. operations research: optimal resource allocation

NP-hard：所有NPC问题可以多项式规约到的问题集合NPhard

之所以NP-complete$\subset$集合，是$P\ne NP$假设下

• HAM-CYCLE 哈密尔顿圈

  不重复点、边的路径访问全部点并回到原点

  有向哈密尔顿-》哈密尔顿圈，