cs6515 Test 3 Questions with Verified Correct
Answers
What is a P problem?
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?
NP = Non-Deterministically Polynomial
-A problem where the Solution can be VERIFIED in Polynomial-Time
What are differences in P and NP?
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?
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?
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?
, 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?
An edge between vertices in the same clause
What is a variable edge?
An edge between complimentary vertices
- x and x' have a variable edge between them.
How to reduce 3SAT to Independent Set?
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?
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.
How to prove S is an independent set?
Answers
What is a P problem?
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?
NP = Non-Deterministically Polynomial
-A problem where the Solution can be VERIFIED in Polynomial-Time
What are differences in P and NP?
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?
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?
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?
, 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?
An edge between vertices in the same clause
What is a variable edge?
An edge between complimentary vertices
- x and x' have a variable edge between them.
How to reduce 3SAT to Independent Set?
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?
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.
How to prove S is an independent set?
