EXAM3

Question 1

A List of Hard problems(NP COmplete)

Answer 1

3SAT
TSP
LOngest Path
3D Matching
Knapsack
IS
Integer Linear Programming
Rudrata Path
Balanced Cut

Question 2

A list of Easy Problems

Answer 2

2SAT, HORN SAT
MST
Shortest Path
Bipartite Matching
Unary Knapsack
Independent set on trees
linear programing
euler path
min cut

Question 3

SAT(C)

Answer 3

Input:C is a CNF with any number of variables and clauses
Output: Assignment of each variable such that the CNF is true

Question 4

3SAT(C)

Answer 4

Input: C is a CNF whose clauses have at most 3 literals
Output: assignment of each variable such that the expression is true

Question 5

CLique(G,k)

Answer 5

Input: G is an undirected unweighted graoh. k is the target size of the IS
Output: CLiquewith >= k vertices

Question 6

Independent Set(G,k)

Answer 6

Input: G is an undirected unweighted graph. is the target size of the IS
Output: IS with >= k vertices

Question 7

Vertex Cover(G,b)

Answer 7

Input: G is an undirected unweighted graph. b in the budget size of the vertex cover

Question 8

Rudrata Path(G)

Answer 8

Input: G is an undirected, unweighted graph
Output: A cycle that visits each vertex in the grph just once

Question 9

TSPSearch(G,b)

Answer 9

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

Question 10

SubsetSum(A, t)

Answer 10

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

Question 11

Knapsack search(W,V, B, g)

Answer 11

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

Question 12

ZOE(A)

Answer 12

Input: An mxn matrix A all of whose entries are 0 or 1 such as Ax=1 where 1 denotes the all-ones vector

Question 13

3D Matching(X,Y,Z)

Answer 13

Input:disjoint sets X,Y,Z of things to be matched. Collection of ordered triples X,Y,Z
Output: Macthes set of triples

Question 14

Difference between IS and CLique

Answer 14

CLique is connected(all edges within S) and IS is disconnected(no edges within S)

Question 15

SAT->3SAT
NP Proof

Answer 15

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)

Question 16

SAT->3SAT
Input

Answer 16

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)

Question 17

3SAT->IS
Output

Answer 17

If 3SAT returns NO return NO for SAT
Return the 3SAT solution without the created variables as the SAT solution

Question 18

3SAT-> IS
Correctness

Answer 18

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.

Question 19

3SAT -> IS
Np Proof

Answer 19

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)

Question 20

3SAT -> IS
Input

Answer 20

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)

Question 21

3SAT -> IS
Output

Answer 21

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

Question 22

3SAT -> IS
Correctness

Answer 22

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

Question 23

VC to IS

Answer 23

Question 24

IS->CLique

Answer 24

Question 25

SAT->3SAT NP and Input

Answer 25

Question 26

SAT->3SAT Output and Correctness

Answer 26