CS6515 EXAM 3 STUDY GUIDE | 2026 UPDATE |
QUESTIONS AND ANSWERS | 100% CORRECT
What is a P problem? Answer - P = Polynomial
-A problem that can be solved in Polynomial time.
-There is a Polynomial time algorithm to solve it.
What is a NP problem? Answer - NP = Non-Deterministically Polynomial
-A problem where the Solution can be VERIFIED in Polynomial-Time
What are differences in P and NP? Answer - All P problems are in NP but all NP
problems are not in P. P is a subset of NP.
-Problems may be verifiable in Polynomial-Time but not solvable in Polynomial-
Time
What are NP-Complete Problems? Answer - The hardest problems in the NP
class.
A problem is NP-Complete if it is in NP and in NP-Hard.
What are NP-Hard problems? Answer - A problem at least as hard as every
problem in the class NP.
A problem is NP-Hard if all other problems in NP can be polynomially reduced
to it.
NP-Hard problems don't have to be NP problems.
, What is the difference between NP-Complete and NP-Hard? Answer - NP-
Complete problems are the hardest in the set NP.
NP-Hard is not necessarily in NP.
NP-Hard problems are at least as hard as everything in the set NP.
What is a clause edge? Answer - An edge between vertices in the same clause
What is a variable edge? Answer - An edge between complimentary vertices
- x and x' have a variable edge between them.
How to reduce 3SAT to Independent Set? Answer - 1. Create a graph
representation of 3SAT input
- 1 vertex for each literal and each clause.
2. Add Clause Edges
-An edge between each literal in a clause
3. Add variable edges
-An edge between x and x'
What vertices do we choose to be in the IS? Answer - 1. No Clause Edges
between vertices.
-Vertices cannot be neighbors of each other.
2. No Variable Edges
-Vertices cannot be compliment of each other
- x and x' cannot both be in IS.
QUESTIONS AND ANSWERS | 100% CORRECT
What is a P problem? Answer - P = Polynomial
-A problem that can be solved in Polynomial time.
-There is a Polynomial time algorithm to solve it.
What is a NP problem? Answer - NP = Non-Deterministically Polynomial
-A problem where the Solution can be VERIFIED in Polynomial-Time
What are differences in P and NP? Answer - All P problems are in NP but all NP
problems are not in P. P is a subset of NP.
-Problems may be verifiable in Polynomial-Time but not solvable in Polynomial-
Time
What are NP-Complete Problems? Answer - The hardest problems in the NP
class.
A problem is NP-Complete if it is in NP and in NP-Hard.
What are NP-Hard problems? Answer - A problem at least as hard as every
problem in the class NP.
A problem is NP-Hard if all other problems in NP can be polynomially reduced
to it.
NP-Hard problems don't have to be NP problems.
, What is the difference between NP-Complete and NP-Hard? Answer - NP-
Complete problems are the hardest in the set NP.
NP-Hard is not necessarily in NP.
NP-Hard problems are at least as hard as everything in the set NP.
What is a clause edge? Answer - An edge between vertices in the same clause
What is a variable edge? Answer - An edge between complimentary vertices
- x and x' have a variable edge between them.
How to reduce 3SAT to Independent Set? Answer - 1. Create a graph
representation of 3SAT input
- 1 vertex for each literal and each clause.
2. Add Clause Edges
-An edge between each literal in a clause
3. Add variable edges
-An edge between x and x'
What vertices do we choose to be in the IS? Answer - 1. No Clause Edges
between vertices.
-Vertices cannot be neighbors of each other.
2. No Variable Edges
-Vertices cannot be compliment of each other
- x and x' cannot both be in IS.
