Exam 3 - NP Reductions Problems

Question 1

If I want to assign bits to objects, choose a subset of objects, or partition objects into two different subsets, what problems might I reduce from?

Answer 1

SAT
k-SAT where k > 2

Question 2

If I want to assign labels to objects from a small fixed set or partition objects into a small number of subsets, what problems might I reduce from?

Answer 2

k-Colorings

Question 3

If I want to find a small subset satisfying some constraints, what problems might I reduce from?

Answer 3

Vertex Cover

Question 4

If I want to find a large subset satisfying some constraints, what problems might I reduce from?

Answer 4

Independent Sets
Clique

Question 5

If the number 3 naturally appears in the problem, what problems might I reduce from?

Answer 5

3SAT

Question 6

If all else fails, what problems might I reduce from?

Answer 6

Knapsack search
3SAT
Subset sum

Question 7

What contradiction proves that it’s impossible to have an algorithm that solves the halting problem?

Answer 7

Assume we have a halting algorithm H, such that
H(Program, Input)
returns true or false depending on whether the program would halt

We write program
D(Program):
if H(P,P):
# infinite loop
else:
return # halts here

Which shows us a contradiction if we run D(D)

Question 8

What is the input of the SAT problem?

Answer 8

boolean formula f in CNF, with n variables and m clauses

Question 9

What is the output of the SAT problem?

Answer 9

A satisfying assignment if one exists, NO otherwise

Question 10

What is the input of the colorings problem?

Answer 10

undirected G = (V,E) and integer k > 0

Question 11

What is the output of the colorings problem?

Answer 11

Assign each vertex a color in {1 , 2 , … , k} so that adjacent vertices get different colors, and NO if no such k-coloring exists for G

Question 12

What is a solution for the Vertex Cover problem?

Answer 12

For a given G = (V,E), the vertices in S, a subset of V, is a vertex cover if they “cover every edge”, for every (x,y) in E either x and/or y is in S

Question 13

What is a solution for the Independent Set problem?

Answer 13

For a given G = (V,E) subset of vertices S from V is an independent set if no edges are contained in S – for any two vertices x and y in S, there is no edge (x,y)

Question 14

What is a solution for the Clique problem?

Answer 14

A clique is a fully connected subgraph – every vertex in the clique is connected to every other vertex

Question 15

What is the knapsack-search problem?

Answer 15

Given input weights {w_1 , … , w_n} and values {v_1 , … , v_n} find a combination of items with weight less than B and value greater than g

Question 16

What is the input and output to the subset sum problem?

Answer 16

input: positive integers a_1, … , a_n , and t
output: subset S of the integers where the sum is equal to t