CS6515 EXAM 3 | QUESTIONS AND ANSWERS | 2026
UPDATE | VERIFIED | 100% CORRECT
The Class P Answer - A solution may be found in polynomial time
The Class NP Answer - A solution may be verified in polynomial time
NP-Hard Answer - We are yet to find a polynomial time solution
NP-Complete Answer - Both in NP and at least as hard as NP-Hard problems
NP Reduction - Steps Answer - 1. Demonstrate that problem B is in the class of
NP Problems
- validate a solution in polynomial time
2. Demonstrate that problem B is at least as hard as a problem believed to be
NP-Complete. This is done via a reduction from a known problem A (A->B)
a) Show how an instance of A is converted to B in polynomial time
b) Show how a solution to B can be converted to a solution for A, again in
polynomial time
c) Show that a solution for B exists IF AND ONLY IF a solution to A exists
, - most prove both parts: if you you have a solution to B, you have a solution to
A
- If there is no solution to B, then no solution exists to A
LP: Why optimum occurs at a vertex Answer - Feasible region is convex
LP: Optimum achieved at a vertex except: Answer - 1. Infeasible - feasible
region is empty
2. Unbounded - optimal value of objective function is arbitrarily large
Independent Set -> Vertex Cover Answer - Lemma: I is an independent set of
G(V, E) iff V - I is a vertex cover of G
Simply check if there is a vertex cover of size V - b in G(V, E). If there is, output
V-S
3SAT -> Independent Set Answer - Lemma: f is satisfiable iff the resulting set
has an independent set of size m (# of clauses in f) in G(V, E).
To construct G(V, E), create a node for each literal in each clause and connect
them by an edge. Also connect any literal with it's negation.
Independent Set -> Clique Answer - Lemma: G(V, E) has an independent set of
size g iff G'(V, E) has a clique of size g.
To construct G'(V, E), add all the vertices in G(V, E) to G'(V, E) and add edges to
G'(V, E) if there is no edge in G(V, E)
SAT Answer - Input: C is a CNF with any # of variables (n) and clauses (m)
UPDATE | VERIFIED | 100% CORRECT
The Class P Answer - A solution may be found in polynomial time
The Class NP Answer - A solution may be verified in polynomial time
NP-Hard Answer - We are yet to find a polynomial time solution
NP-Complete Answer - Both in NP and at least as hard as NP-Hard problems
NP Reduction - Steps Answer - 1. Demonstrate that problem B is in the class of
NP Problems
- validate a solution in polynomial time
2. Demonstrate that problem B is at least as hard as a problem believed to be
NP-Complete. This is done via a reduction from a known problem A (A->B)
a) Show how an instance of A is converted to B in polynomial time
b) Show how a solution to B can be converted to a solution for A, again in
polynomial time
c) Show that a solution for B exists IF AND ONLY IF a solution to A exists
, - most prove both parts: if you you have a solution to B, you have a solution to
A
- If there is no solution to B, then no solution exists to A
LP: Why optimum occurs at a vertex Answer - Feasible region is convex
LP: Optimum achieved at a vertex except: Answer - 1. Infeasible - feasible
region is empty
2. Unbounded - optimal value of objective function is arbitrarily large
Independent Set -> Vertex Cover Answer - Lemma: I is an independent set of
G(V, E) iff V - I is a vertex cover of G
Simply check if there is a vertex cover of size V - b in G(V, E). If there is, output
V-S
3SAT -> Independent Set Answer - Lemma: f is satisfiable iff the resulting set
has an independent set of size m (# of clauses in f) in G(V, E).
To construct G(V, E), create a node for each literal in each clause and connect
them by an edge. Also connect any literal with it's negation.
Independent Set -> Clique Answer - Lemma: G(V, E) has an independent set of
size g iff G'(V, E) has a clique of size g.
To construct G'(V, E), add all the vertices in G(V, E) to G'(V, E) and add edges to
G'(V, E) if there is no edge in G(V, E)
SAT Answer - Input: C is a CNF with any # of variables (n) and clauses (m)
