Example
Fibonacci Numbers - FIB1(n)
if n = 0 then
return 0
else if n = 1 then
return 1
return FIB1(n − 1) + FIB1(n − 2)
이 코드에 대해 다음 질문을 하게된다.
=> O(2^n) or exponential
Fibonacci Numbers - FIB2(n)
if n = 0 then
return 0
create an array f[0, ... , n]
f[0] = 0, f[1] = 1
for i = 2, ... , n do
f[i] = f[i − 1] + f[i − 2]
return f[n]
=> O(n)
Search Problems
P and NP
An instance of SAT is a Boolean formula in CNF (conjunctive normal form).
SAT problem: Given a Boolean formula in CNF, either find a satisfying true assignment or report “none exists”.
SAT is a typical search problem: We are given an instance I, and we are asked to find a solution S.
Property of a search problem: Any proposed solution S to an instance I can be quickly checked for correctness. That is, there is a polynomial-time algorithm that takes as input I and S, and decides whether or not S is a solution for I.
지난 50년 동안 효과적인 방법을 찾으려고 했지만 성공하지 못했다. 가장 빠른 알고리즘도 지수만큼 최악이다. But, interestingly, there are two natural variants of SAT for which we have good algorithms.
Horn formula. All clauses contain at most one positive literal. A greedy algorithm can find a solution in linear time.
2SAT. All clauses have only two literals. Can be solved in linear time by finding the strongly connected components.
An instance of TSP consists of n vertices and all n(n−1)=2 distances between them.
TSP problem. Given a set of n vertices and their pairwise distances, find a shortest tour (a permutation of vertices) that passes through every vertex exactly once.
TSP as a Search problem. Given a set of n vertices, their pairwise distances, and a budget b, find a tour of total cost b or less that passes through every vertex exactly once, or report “no such tour exists”.
A dynamic programming algorithm takes O((n^2)*(2^n)) time, which is slightly better than (n − 1)!. But no polynomial time algorithm is known yet.
Euler Path problem: Given a graph, find a path that contains each edge (선) exactly once.
Euler Path: A connected undirected graph has an Eulerian cycle iff every vertex has even degree.
Rudrata Cycle problem: Given a graph, find a cycle that passes through every vertex (꼭지점) exactly once.
There are two differences from the Euler problem.
– Euler’s problem visits all edges while Rudrata’s visits all vertices.
– Euler’s demands a path while Rudrata’s requires a cycle.
This is a reminiscent of the TSP, and indeed no polynomial time algorithms is known for it. But a proposed solution can be quickly checked.
A cut is a set of edges whose removal leaves a graph disconnected.
Minimum Cut problem: Given a graph and a budget b, find a cut with at most b edges.
Balanced Cut problem: Given a graph with n vertices and a budget b, find a cut (A, B) such that |A|, |B| >= n/3 and at most b edges in the cut.
Balanced cuts arise in a variety of important applications, such as clustering and and image segmentation. However, no polynomial-time algorithm is known for it. But a proposed solution can be quickly checked.
3D Matching problem: Given n boys and n girls but also n pets, and the compatibility among them, find n disjoint triples
Independent Set problem: Given a graph and a goal g, find g vertices that are independent, that is, no two of which have an edge between them.
Vertex Cover problem: Given a graph and a budget b, find b vertices that cover (touch) every edge
Clique problem: Given a graph with n vertices and a budget b, find a set of b vertices such that all possible edges between them are present.
Longest Path (aka Taxicab Rip-off) problem: Given a graph with nonnegative edge weights and two vertices s and t, along with a goal g, find a simple path from s to t with total weight at least g.
Subset Sum problem: Given a set of integers and a value W, find a subset of integers that adds up to exactly W.
Property of a search problem: Any propsed solution S to an instance I can be quickly checked for correctness.
Most researchers believe P != NP. But no proof. Then why they believe so?
Reduction provides some evidence
Reduction, A → B, has two purposes :
Reductions have the composition property: If A → B and B → C, then A → C
A search problem is NP-complete if all other search problems reduce to it.