[TOC]

# 1. Introduction to Intractability

recall model of computation: DFA
a univeral model of computation: turing machine
→ no more powerful model of computation.
Turing machine can compute any function that can be computed by a physically harnessable process of the natural world.

bottom line: turing machine is a simple and universal model of computation.

Q. which algos are useful in practice?

useful in practice = polynomial time for all inputs

def. a pb is intractable if it cannot be solved in polynomial time.

2 pbs that can be proved to require exp time:

1. Given a constant-size programme, does it halt in <=K steps ?
2. Given a N*N chess board position, can the first player force a win ?

Bad news: very few pbs can be proved to require exp time...

# 2. Search Problems

Four fundamental problems:

• LSLOVE

Given a system of linear equations, find a solution
var: real numbers
→ guassian elimination

• LP

Given a system of linear inequaties, find a solution. (not necessarily find the opt)
var: real numbers

• ILP

Given a system of linear inequaties, find a 0-1 solution.
var: 0 or 1

• SAT

Given a system of boolean equations, find a binary solution.

Which ones of the 4 foundamental pbs have poly-time solutions?

• LSLOVE: Gaussian elimination works in O(n3)
• LP: Ellipsoid works in poly-time (simplex also poly-time in practice..)
• ILP, SAT: No poly-time algorithm known (or believed to exist) !

All 4 pbs are examples of search problems.

Search pb: given an instance `I`, find a solution `S` / report there's no solution.
requirement: able to efficiently (poly-time) check that `S` is a solution. (that's the case for the above 4 fundamental pbs)

another example:
FACTOR: given a n-bit integer, find a nontrival factor.
(given a solution, simply need to long-divide to check...)

# 3. P vs. NP

def. NP is the class of all search pbs. (ie. solution be checked efficiently)
NB: classical definition limits to yes-no pbs...
Significance: NP pbs are what scientists and engineers aspire to compute feasibly.
examples: def. P is the class of search pbs that are solvable in poly-time.

(What scientists and engineers do compute feasibly.)

examples: Nondeterminism
Nondeterminism machine can guess the solution (donot exist in natural world..). → NFA tries to simulate such a machine...
Ex. `int[] a = new int[N];`
・ Java: initializes entries to 0 .
・ Nondeterministic machine: initializes entries to the solution! NP: Search problems solvable in poly time on a nondeterministic Turing machine.

Extended Church-Turing thesis:
P: Search pbs solvable in poly time in natural world.

do we have non-determinism in natural world? ---> natural computers ?
ex. STEINER tree: set of segments connecting given N points.
use soap → doesn't really work... another example for P/NP: automating creativity
being creative VS appreciating creativity The central question: does P=NP?
(can you alway avoid brute-force searching and do better?) Millennium prize by Clay instute.
(among all ways of earning 1M dollars, this might be the most complicated way... @_@...)

# 4. Classifying Problems

classify pbs like classifying elements into perodic table.

key pb: satisfiablity
SAT. given a sys of boolean eq, find a solution.

exhaustive search: try 2^n possible solutions.
conjecture: no poly-time algo for SAT (ie. intractable)

Assumption: assume the intractability for SAT.
Tool: reduction
def. pb X reduces to pb Y: we can solve pb X with the algo for pb Y. if SAT poly-reduces to pb Y ⇒ pb Y in (probably) intractable.

### SAT poly-reduces to ILP (all SAT pb can be reduced to 3SAT)

⇒ can be converted to an ILP pb:
for each eq, introduce a var Ci:    # 5. NP-Completeness

def. an NP pb is NP-complete if all pbs in NP poly-reduces to it.

prop. SAT id NP-complete.
any pb in NP poly-reduces to SAT (reverse direction as last lecture)
pf sketch: convert non-dertiministic turing machine notation to SAT notation...

cor. poly time algo for SAT iff P=NP... ⇒ there pbs are equivalent !  summary: ==... # 6. Coping with Intractability

### exploit intractability

cryptography ecopoits the hardness of FACTOR pb Can factor an n-bit integer in n 3 steps on a "quantum computer.”

### Coping with intractability

relax one of desired features...

• special cases • Develop a heuristic, and hope it produces a good solution.

no guarantee
ex. TSP

• Approximation algorithm. Find solution of provably good quality. ### Halmiton path

remark: Euler path (each edge once) easy, Halmiton path (each vertex once) NPC...
dfs solution for Halmiton path:

```public class Halmiton{
private boolean[] marked;
private int count=0; // nb of Halmiton paths
public Halmiton(Graph G){
marked = new boolean[G.V()];
for (int v=0; v<G.V(); v++)
dfs(G,1,1);
}
private void dfs(Graph G, int v, int depth){
if(depth==G.V()) count++;
marked[v]=true;
for(int w: G.adj(v))
if(marked[w]==false) dfs(G, w, depth+1);
marked[v]=flase; // backtrack
}
}
``` #### Part 13 of series «Algorithms Princeton MOOC II»：

comments powered by Disqus