跳转至

NP Completeness

  • Decision problem (yes/no)
  • Search problem (find the answer)
  • Optimization problem

Nondeterministic Turing machine

  • A Deterministic Turing Machine executes one instruction at each point in time. And then depending on the instruction, it goes to the next unique instruction.
  • A Nondeterminism is now typically represented by giving a machine an extra input, the certificate or witness.

NP

  • NP: Nondeterministic polynomial-time
  • NP Problem: 在 polynomial-time 时间内可以验证的问题。
  • \(NP \overset{?}{=} P\): 是否所有能在 polynomial-time 时间内验证的算法都能在 polynomial-time 内被解决

Reduction and NP-Complete Problems

An NP-complete problem has the property that any problem in NP can be polynomially reduced to it.

reduction 约化

To prove a reduction \(A\le_P B\) , we require 3 steps

  1. We have to find the mapping function \(f\) and show that it runs in polynomial time.
  2. for all \(x \in A\), then \(f(x) \in B\)
  3. If \(f(x)\in B\), then \(x\in A\)

如果 \(Q_1\le_p Q_2\), 我们可以认为：

  • A polynomial-time algorithm for \(Q_2\) would sufficiently imply a polynomial-time algorithm for \(Q_1\).
  • \(Q_1\) can be polynomially reduced to \(Q_2\)

常见 NPC 问题

  • SAT Problem(第一个被证明为 NPC 的问题): 给定一个n个布尔变量组成的布尔表达式，判断其有没有可能为真
  • Hamiltonian cycle Problem: 给定一个图，判断是否有一个simple cycle恰好经过每个顶点一次
  • Traveling Problem: 给定一个带权图，问是否存在一个simple cycle经历过每个节点且经历边的权重和不超过K?
  • Vertex Cover Problem: 给定一个图，判断是否存在其一个大小不超过K的点集，使得图中任一条边至少有一个顶点在这个点集中
  • clique problem: 给定一个图，判断图是否有一个大小至少为K的完全子图（团）。

NP-Hard

If a NP-Hard problem is in NP, it is a HP-complete problem.

常见NP-hard问题

  • 所有NP-Complete问题
  • Halting problem(不属于NP-Complete)

Formal-language Theory*

  • An alphabet \(\Sigma\) is a finite set of symbols
  • A language \(L\) over \(\Sigma\) is any set of strings mode up of symbols from \(\Sigma\)
  • Denote empty string be \(\varepsilon\)
  • Denote empty language by \(\emptyset\)
  • Language of all strings over \(\Sigma\) is denoted by \(\Sigma^{\star}\)
  • The complement of \(L\) is denoted by \(\Sigma^{\star}-L\)
  • The concatenation of two languages \(L_1\) and \(L_2\) is the language \(L=\{x_1x_2: x_1\in L_1\ {\rm and}\ x_2\in L_2\}\)
  • The closure of Kleene star of a language \(L\) is the language \(L^{\star}=\{\varepsilon\}\cup L\cup L^2\cup L^3\cup \cdots\), where \(L^k\) is the language obtained by cocncatenating \(L\) to itself \(k\) times