EXAM3 Flashcards
A List of Hard problems(NP COmplete)
3SAT
TSP
LOngest Path
3D Matching
Knapsack
IS
Integer Linear Programming
Rudrata Path
Balanced Cut
A list of Easy Problems
2SAT, HORN SAT
MST
Shortest Path
Bipartite Matching
Unary Knapsack
Independent set on trees
linear programing
euler path
min cut
SAT(C)
Input:C is a CNF with any number of variables and clauses
Output: Assignment of each variable such that the CNF is true
3SAT(C)
Input: C is a CNF whose clauses have at most 3 literals
Output: assignment of each variable such that the expression is true
CLique(G,k)
Input: G is an undirected unweighted graoh. k is the target size of the IS
Output: CLiquewith >= k vertices
Independent Set(G,k)
Input: G is an undirected unweighted graph. is the target size of the IS
Output: IS with >= k vertices
Vertex Cover(G,b)
Input: G is an undirected unweighted graph. b in the budget size of the vertex cover
Rudrata Path(G)
Input: G is an undirected, unweighted graph
Output: A cycle that visits each vertex in the grph just once
TSPSearch(G,b)
Input: G is an undirected weighted graph. b is the budget cost of the path
Output: A cycle that visits each vertex in the graph exactly once and returns to the original vertex and has a total cost <= b
SubsetSum(A, t)
Input: A is an array of integers. t is the target integer sum
Output: An array of integers which is a subset from A that sum to t
Knapsack search(W,V, B, g)
Input:W is the array of weights. V is the array of values. B is the capacity of the knapsack. g is the target value
Output: Array of items of total weight <= B and total value >= g
ZOE(A)
Input: An mxn matrix A all of whose entries are 0 or 1 such as Ax=1 where 1 denotes the all-ones vector
3D Matching(X,Y,Z)
Input:disjoint sets X,Y,Z of things to be matched. Collection of ordered triples X,Y,Z
Output: Macthes set of triples
Difference between IS and CLique
CLique is connected(all edges within S) and IS is disconnected(no edges within S)
SAT->3SAT
NP Proof
GIven an input we look for a solution if it exsits and return NO if it doesn’t
Given an input I to 3SAT and a solution S, we can tale each T/F assignent from S and check them in each clause of I. It is O(1) to check each clause. m clauses results in O(m)
SAT->3SAT
Input
Let c in C be clauses in the input I
Let c’ in C be clauses in our input to 3SAT
for each c in C
if c has k<= 3 literals, c’=c
if c has k >3 literals:
create k-3 new variables as y1, y2…yk-3
c’ = (X1 v X2 v Y1) ^ (!Y v X3 v Y2) ….. (!yk-4 v Xk-2 v Yk-3)….
Replacing n varaibles - O(n)
Replacing m clauses - O(m)
3SAT->IS
Output
If 3SAT returns NO return NO for SAT
Return the 3SAT solution without the created variables as the SAT solution
3SAT-> IS
Correctness
FOr each c’ that is set to the original c, no logic is changed. For each c’ that is set to a conversion of c, if ci-1 has all false literals for X in c, then yi-1 must be set to true to satisfy ci-1. So then c’i must have !yi-1 set to false. So then either X in ci is true or yi is true. This carries forward until c’ and c are satisified by some X in c being set to true. This shows that c’=c are satisified by some X in c being set to true. This shows c’’ = c. If c’= C then c’ is satisified in 3SAT then C is satisified in SAT. If C’ is not satisified in 3SAT then C is not satisified in SAT. This proves that 3SAT is NP-Complete.
3SAT -> IS
Np Proof
GIven an input, we look for a solution if it exists an return NO if not
GIven an input G=(V,E), g to IS and a solution S, we can verify that for all pairs x,y in S that (x,y) not in E. This takes O(n^2) time. We can check that |S|>= g in O(n) time. Overall, O(n^2)
3SAT -> IS
Input
Let c in C be clauses in the input I. For each c in C:
Encode c into edges of a graph such that each literal in c are connected by undirected edges to each literal. O(m)
We want to prevent literals fro contradicting each other. For each variable x, add an edge between all literals X and all !X. This takes O(nm) to check every clause for every variable
Finally, we need a target g for the IS problen. We use g=m where m is the number of clauses in the 3SAT. Satisfying m clauses requires a g sized independent set of variables. This takes O(m)
Total O(nm)
3SAT -> IS
Output
If the IS algorithm returns NO then the 3SAT algorithm also returns NO.
For a solution S to the IS algorithm, take each vertex in S assign the atching literal in the 3SAT to True. This takes O(n) polynomial
3SAT -> IS
Correctness
If the IS algorithm is able to find g vertices that do not neighbor each other, then that means v in S are not hte same clauses nor do they contradict each other. This is how we constructed G. Then setting each corresponding literal to True in the 3SAT would result in a valid assignment that satisifies each clause and has no contradictions. If the IS algo retturns NO then it could not find a IS that is >= g and so the 3SAT will not be able to assign a literal in each clause to True without some contradiuction
This is due to us setting g=m to satisfy all clauses. Then there must be an IS of least size g found. This proves NO complete
VC to IS
IS->CLique
SAT->3SAT NP and Input
SAT->3SAT Output and Correctness