Exam 3 Part 1 Flashcards
What is the difference between P and NP? What is a search problem?
NP = class of all search problems
P = class of search problems that are solvable in polynomial time
Search problem: problem that we can efficiently verify solutions
Given an instance I, find a solution S that matches input I
- if a solution exists return S, if not return NO
- we can verify the solution S paired with I in polynomial time
- polynomial of the input size
What does it mean when P = NP or P != NP?
- every search problem lies in NP and P is a subset of NP
P = NP:
- implies if I can check the solution in polynomial time, then I can generate the solution in polynomial time
- all problems in the class of NP are also in P
- hard to prove the problem is P
P != NP:
- means the separation area between P and NP is not NP
- there are some problems that can not be solvable in polynomial time
- the problems that lie in between are NP-complete problems
What are the NP-complete problems? What is the difference between NP-complete and NP-hard?
The problems that lie in between P and NP classes; they are the hardest problems in the class NP
NP-Complete Problems
Definition: A problem is NP-complete if it satisfies two conditions:
It is in NP: This means that given a solution, we can verify its correctness in polynomial time.
It is NP-hard: This means that every problem in NP can be reduced to this problem in polynomial time.
Significance: NP-complete problems are the “hardest” problems in NP in the sense that if we can find a polynomial-time algorithm to solve any NP-complete problem, then we can solve all problems in NP in polynomial time (i.e.,
𝑃
=
𝑁
𝑃
P=NP).
Examples:
The Boolean satisfiability problem (SAT)
The Traveling Salesman Problem (decision version)
The Clique Problem
NP-Hard Problems
Definition: A problem is NP-hard if every problem in NP can be reduced to it in polynomial time.
Significance: NP-hard problems are at least as hard as NP-complete problems, but they do not have to be in NP. This means an NP-hard problem might not have solutions that can be verified in polynomial time.
Examples:
The Halting Problem (which is undecidable)
The Optimization version of the Traveling Salesman Problem (TSP)
Certain scheduling problems
What is the SAT problem? Is is it in the class P and NP?
SAT is in the class NP but unknown if it’s in P
- can verified in O(nm) time
- no algorithm can solve in polynomial time yet
SAT:
input: CNF formula m clauses and n liters
output: satisfying if one exists; NO if none exist
What is the k-colorings problem? Is is it in the class P and NP?
input: undirected graph G(V,E) and integer k > 0
output: graph where each vertex is assigned a color in {1, 2 …k} where each adjacent vertex has different colors assigned; if no such assignment exists return NO
problem is in class NP because it can be verified in O(m) time where m is the edge length (we check all edges)
For k = 2, the problem is in P because there’s a polynomial algorithm to solve it
But not for k >= 3 (unless P = NP)
What is the MST problem? Is is it in the class P and NP?
MST = minimum spanning tree problem
input: undirected weighted graph G(V,E)
output: MST where all vertices are covered where the minimum total amount of edges are used (min weight tree)
In both classes P and NP
NP because we can run BFS/DFS to check if the output is a tree O(m + n) time
P because we can use Kruskal’s or Prim’s algorithm to find the MST O(m log n)
What is the Knapsack problem? Is is it in the class P and NP?
input: n objects with integer weights wi to wn and integer values vi to vn and a given capacity B
output: subset S of objects with total weight <= B and max total value (with or without repetition)
Knapsack is not in both NP or P because we can’t verify in polynomial time of the input size
What is the Knapsack search? Is is it in the class P and NP?
input: n objects with integer weights wi to wn and integer values vi to vn and a given capacity B AND goal g
output: subset S of objects with total weight <= B and total value (with or without repetition) at or greater than goal g ; otherwise NO
Knapsack search is in NP because we verify a solution in overall linear time O(n); not sure about P
The statement “SAT is NP-complete” means…
a) we can verify the solution for SAT in polynomial time
b) if we can solve SAT in polynomial time then we can solve every problem in NP in polynomial time
What are reductions and what is their purpose? How do we do it?
Based on the premise that if we can solve problem B in polynomial time then we can solve problem A in polynomial time using that algorithm
This is reducing from A to B
ex) k-colorings = A to B = SAT
How:
- we use the algorithm solving problem B (SAT in this case) as a black box algorithm
- input to A is transformed as an input to B (this is F(I) )
- output to B S is transformed to the output of A h(S)
- the transformations must be done in polynomial time to prove the reduction works
We need to prove:
S is a solution of F(G, k) <=> (if and only if) h(S) is a solution to (G, k)
T or F; we can reduce SAT to IS
True
What is the 3SAT problem? is is in the class NP and P?
input: CNF formula with n vars and m clauses where each clause has <= 3 variables
output: satisfying assignment if one exists and NO if one does not
3SAT is in the class NP
because we can reduce SAT to 3SAT and verify the solution in polynomial time O(m)
Unlikely to be in P
How is the reduction from 3SAT to SAT completed?
3SAT: A specific case of SAT where each clause has exactly three literals.
Take a CNF input called f
keep C1 and C3 clauses the same
Modify C2 with a new variable y to create new C2’
where you have claim C2 is satisfiable <=> C2’ is satisfiable
The same process can be done for reducing 5SAT to 3SAT where
in general
create k-3 variables y1, y2, …yk-3 and replace C by k-2 clauses
What is the independent set problem? Is it in NP?
input: undirected graph (V,E)
output: independent set S of maximum size
It is not known to be in NP
How can we show that the IS problem is NP-complete?
Given the solution S to the IS problem, we can verify the solution in O(n^2) time by checking all pairs x,y E in S and verify that the pairs do not have an edge in E and check in O(n) time that |S| >= g
Also reduce 3SAT to IS
How to:
- 3SAT CNF formula with xn vars and cn clauses (each clause as 3 or less vars)
- we define a graph G and set g = m
- for each clause ci, create |ci| vertices
In other words, we create a vertex for each literal in each clause
The clauses make up a subgraph where the literals are vertices and the edges connect to other literals in the clause
We then add edges between the complementary literals and their respective literals ex) x and x_bar
We then set the IS size as size m or the number of clauses
Example:
To satisfy the 3SAT formula, select one vertex from each clause without selecting any adjacent vertices
The selected vertices form an independent set of size 2, corresponding to a satisfying assignment for the 3SAT formula
What is the clique problem and is it part of the NP group?
Input: G(V,E) undirected and goal g size
Output: subset of V where S is the clique of size g or larger if one exists; else NO
The clique problem is not known to be in the NP class but we can show that it’s NP-complete via reduction
How can we reduce IS to clique problem?
Key idea: Clique is the opposite of an IS and vice versa
Thus we can prove that:
S is a clique in G <=> S is a IS in Gbar
where Gbar is a graph where the edges in G are flipped (remove edges between vertices that have them and add edges between verties that don’t have them)
Proving clique problem is NP-complete:
We can verify that the subset has edges between all pairs in S in O(n^2) time and check in O(n) time the size of S
Input transformation:
construct Gbar from G and input to IS problem
output transformation:
Take soluton S and return for clique problem for graph G
What is the Vertex Cover problem and is it in NP?
input: G(V,E) and budget b
output: subset S of vertices that cover all edges in the graph of size <= b ; else NO
In the class NP because it can be validate in polynomial time
What problem has a direct relationship with the vertex cover problem where a reduction could happen? How?
Independent Set can be reduced with vertex cover
First) Vertex cover is NP-complete:
Output S can be verified and checked every x,y pairing is in E where x and y are in S (take O(n+m) runtime)
Also takes O(n) time to verify <= b
S is a vertex cover in G <=> Sbar is an independent set
No Sbar edges in S and thus Sbar is an IS
What is the subset problem and is it in P and NP?
input: positive integers a1..an and t
output: subset S of {1..n} where sum ai = t if such as subset exists
No otherwise
Not in P
In NP -> verified O(n log t) time
What problem can be reduced with the subset problem? What are the steps to do so?
(card incomplete)
3SAT
Steps:
Input to subset: 2n + 2m + 1 numbers
v1, v1bar, v2, v2bar, … vn, vnbar, s1, s1bar, …sm, smbar and t
all are <= n+m digits long & base 10
t ~ 10^n+m
vi corresponds to xi
vibar corresponds to xibar
Thus
vi is in S <=> xi is True
vibar is in S <=> xibar is False
digit n+j corresponds to clause Cj
if xi in Cj then put 1 in digit n+j for vi
if xibar in Cj then put 1 in digit n+j for vibar
put 3 in digit n+j of t
Put O in digit n+j of other numbers
subset-sum has a solution <=> 3SAT f is satsifiable
Take the solution S of the subset-sum and then:
- for digit n+j where 1<= j <= n
to get sum of 3 in digit n+j
need to include >= 1 literal of
Is there an algorithm that takes polynomial time on every input for an NP problem?
NO
What are undecidable problems?
Problems that are computationally impossible; there is no algorithm that solves a problem on every input regardless of the run time
What is the halting problem?
This is an example of a undecidable problem
input: a program (any language) with input I
output: True if P(I) ever terminates; False otherwise (has an infinite loop)
ex) while x % 2 == 1 {
x += 6
}
let x = 5
it never stops so then
Halting (P,5) = False
How do we prove that the halting problem is undecidable?
By contradiction
Derive algorithm Terminator(P,I)
We can construct a program Q and input J where when we run terminator(Q, J) is incorrect (terminator is a black box)
What is the HP paradox?
If Harmful(Harmful) terminates, then Harmful(Harmful) never terminates
If Harmful(Harmful) never terminates, then Harmful(Harmful) terminates
Thus program terminator program exists is impossible
