Vincec's Dimension

Algorithm Review Notes - NP Problem

Word count: 859 / Reading time: 5 min
2018/11/26 Share

NP Hardness

Church-Turing Thesis

  • Any natural/reasonable notion of computation can be simulated by a Turing Machine.
  • Not a theorem
  • No counterexample yet

Deterministic Turing Machine

There is only one valid computation starting from any given input.

Nondeterministic Turing Machine

The computation can be a tree at any state, allowing to have a number of choices.

Can have try out many possible computation in parallel for accpeting any one of these as a input.

Complexity class NP

A class of decision problems that can be solved by a nondeterministic turing machine in polynomial time

Or described as

NP decision problem can be checked by a polynomial time deterministic Turing Machine

P VS. NP Problem

Nondeterministic Turing Machine can be simluated by deterministic Turing Machine

P != NP Thought

We cannot simluate nondeterministic Turing Machines in polynomial time.

Undecidable Problems

There is no computer program that always gives the correct answer. (We can not prove)

Halting Problem

Deciding whether a given turing machine halts or not.

Polynomial Reduction (Proving NP completeness)

  • Y ≤p X
  • Y ->p X
  • Y ->T X, where T is to do reduction
  • Reduce Y to X
  • If X then Y / If not Y, then not X
  • X is at least hard as Y, or at least easy as Y (we can not discuss easy because if that is the case, we can slove Y in polynomial time)
  • If we can slove X in polynomial time. we can slove Y in polynomial time. E.g. Bipartite Matching ≤p Max-Flow, cirulation ≤p Max-Flow

Steps:

  • Reduce an input Y into an input of X
  • Solve X,
  • Reduce the solution back to Y

P, NP, NP-Hard & NPC

P:

  • set of problems that can be solved in polynomial time by a deterministic Turing Machine

NP

  • set of problems that can be solved in polynomial time by a nondeterministic Turing Machine
  • set of problems that their solutions can be verified in polynomial time by a deterministic Turing Machine

NP-Hard

  • X is NP-Hard if ∀Y ∈ NP and Y ≤p X (Polynomial Reduction)
  • Solution of X is not varified
  • X is at least hard as Y

NP-Complete

  • X is NPC if X is NP-Hard and X ∈ NP
  • Solution of X is varified
  • NPC can be solved by a nondeterministic Turing Machine in polynomial time.


source

Venn Diagram (P, NP)

NPH (Not have to be in NP)

  • Undecidable: Halting Problem
  • TSP, optim

NPC (NPC ⊆ NP-Hard, Most difficult NP Problems)

  • SAT
  • Set Cover
  • Vertex Cover

NP (not P and NPC part)

  • Graph isomorphism
  • Factorization Discrete Log

Prove NP-Completeness

  1. Show that X is in NP
  2. Pick a problem Y, known to be an NP-C
  3. Prove Y ≤p X (Reduce a NP-C to a harder NP-C)

Cook-Levin Theorem

Conjunctive Normal Form (CNF) satisfiability (SAT) is NP-C [Can be check/vertify in linear time, but can not be solve]

Independent Set

Find the set of vertex that no edge joining together.

NP-Hard Verison (to find solution)
Find the largest independent set

NPC Version (To verify)
Given a graph and a number k, does…contain independent set with size k?

Proving is NP
Showing can verify a solution in poly time

Proving is NP-Hard
Pick Y from NP such that Y can reduce to Independent set, Y can be 3-SAT

Proving is NPC
X is NP-Hard and X ∈ NP -> X is NPC

Vertex Cover

Theoerm: s is independent set iff v-s is a vertex cover.

NP-Hard Verison (to find solution)
Given G=(V, E), find the smallest set in V

NPC Version (To verify)
Given G and number k, does the graph contains a vertex cover of size at most k?

Proving is NPC
By the theoerm, we can make a Polynomial Reduction:

  • Independent Set ≤p Vertex Cover, Vertex Cover is at least hard as Independent Set (thought was same in this example)
  • Independent Set is NPC -> Vertex Cover is NPC

Graph Coloring

Theorem: K>2. K coloring is NPC

Prove:
3-SAT ≤p 3-Colorable

Claim:
3-SAT instance is satifiable iff G is 3-colorable

Sudoku

sudoku ≤p 9-colorable

Not prove that Sudoku is NP-Complete, Sudoku is Y

Hamiltonian Cycle

A cycle in the graph that visits each vertex exactly once

NPC Version
Given directed or undirected G = (V, E), Find if graph contain a HC?

Prove:

  • SAT ≤p Hamiltonian Cycle
  • HC is NPC

Traveling Salesman Problem - TSP

Salesman travel and only go one route once, want to have smallest weight.

NPC Version
Given a weighted G = (V, E), is there a HC that has total cost ≤ k?

Prove:

  • Hamiltonian Cycle ≤p TSP (Might)
  • TSP is NPC

Related Read

  1. 算法课笔记系列(八)——NP问题及其计算复杂性
  2. P问题、NP问题、NPC问题的概念即实例证明 - 综合编程类其他综合 - 红黑联盟](https://www.2cto.com/kf/201605/511207.html)
  3. Proof that Hamiltonian Path is NP-Complete
  4. Hamiltonian Path is Hard 2

Reference

  • slides
CATALOG
  1. 1. NP Hardness
    1. 1.1. Church-Turing Thesis
    2. 1.2. Deterministic Turing Machine
    3. 1.3. Nondeterministic Turing Machine
    4. 1.4. Complexity class NP
    5. 1.5. P VS. NP Problem
      1. 1.5.1. P != NP Thought
    6. 1.6. Undecidable Problems
      1. 1.6.1. Halting Problem
  2. 2. Polynomial Reduction (Proving NP completeness)
  3. 3. P, NP, NP-Hard & NPC
  4. 4. Venn Diagram (P, NP)
    1. 4.1. NPH (Not have to be in NP)
    2. 4.2. NPC (NPC ⊆ NP-Hard, Most difficult NP Problems)
    3. 4.3. NP (not P and NPC part)
    4. 4.4. Prove NP-Completeness
  5. 5. Cook-Levin Theorem
  6. 6. Independent Set
  7. 7. Vertex Cover
  8. 8. Graph Coloring
  9. 9. Sudoku
  10. 10. Hamiltonian Cycle
  11. 11. Traveling Salesman Problem - TSP
  12. 12. Related Read
  13. 13. Reference