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
