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

• 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