Name: Score:
21 Multiple choice questions
Term 1 of 21
What is Rudrata Cycle problem?
An edge between complimentary vertices
- x and x' have a variable edge between them.
Find a CYCLE that visits each VERTEX exactly once.
-No Known Polynomial Time algorithm
Find a PATH that contains each EDGE exactly once.
-Can be solved in Polynomial Time
Same as Rudrata cycle except find a PATH.
,Term 2 of 21
What vertices do we choose to be in the IS?
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'
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.
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.
1. Max-Independent-Set
2. Clique
3. Vertex Cover
4. SAT
5. 3SAT
6. Independent Set
,Term 3 of 21
What are the claims of 3SAT reduction to Independent Set?
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.
- 3SAT input, f, has a satisfying assignment <==> G has an independent set of size ≥ g
- g = m = # of clauses
1. Max-Independent-Set
2. Clique
3. Vertex Cover
4. SAT
5. 3SAT
6. Independent Set
The hardest problems in the NP class.
A problem is NP-Complete if it is in NP and in NP-Hard.
Term 4 of 21
What is a variable edge?
Find a PATH that contains each EDGE exactly once.
-Can be solved in Polynomial Time
NP = Non-Deterministically Polynomial
-A problem where the Solution can be VERIFIED in Polynomial-Time
An edge between vertices in the same clause
An edge between complimentary vertices
- x and x' have a variable edge between them.
Term 5 of 21
What is a clause edge?
A type of punctuation used to indicate a clause
A graphical representation of all clauses in a legal contract
A boundary that separates different clauses in a document
An edge between vertices in the same clause
, Term 6 of 21
What is Euler Path Problem?
Find a CYCLE that visits each VERTEX exactly once.
-No Known Polynomial Time algorithm
An edge between complimentary vertices
- x and x' have a variable edge between them.
Same as Rudrata cycle except find a PATH.
Find a PATH that contains each EDGE exactly once.
-Can be solved in Polynomial Time
Term 7 of 21
How to prove S is an independent set?
1. Prove the problem is in NP
-Given problem and solution, Verify solution in Polynomial Time.
2. Prove problem is as hard as any NP-Complete problem. (K nown → New)
-Show reduction from known NP-Complete problem to this problem.
-Use a problem similar to this one.
-Prove forward and backward implication.
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'
-S has exactly 1 vertex per clause
-Both x₁ and x₁' are not in S.
-|S| = m = g
1. Max-Independent-Set
2. Clique
3. Vertex Cover
4. SAT
5. 3SAT
6. Independent Set
21 Multiple choice questions
Term 1 of 21
What is Rudrata Cycle problem?
An edge between complimentary vertices
- x and x' have a variable edge between them.
Find a CYCLE that visits each VERTEX exactly once.
-No Known Polynomial Time algorithm
Find a PATH that contains each EDGE exactly once.
-Can be solved in Polynomial Time
Same as Rudrata cycle except find a PATH.
,Term 2 of 21
What vertices do we choose to be in the IS?
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'
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.
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.
1. Max-Independent-Set
2. Clique
3. Vertex Cover
4. SAT
5. 3SAT
6. Independent Set
,Term 3 of 21
What are the claims of 3SAT reduction to Independent Set?
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.
- 3SAT input, f, has a satisfying assignment <==> G has an independent set of size ≥ g
- g = m = # of clauses
1. Max-Independent-Set
2. Clique
3. Vertex Cover
4. SAT
5. 3SAT
6. Independent Set
The hardest problems in the NP class.
A problem is NP-Complete if it is in NP and in NP-Hard.
Term 4 of 21
What is a variable edge?
Find a PATH that contains each EDGE exactly once.
-Can be solved in Polynomial Time
NP = Non-Deterministically Polynomial
-A problem where the Solution can be VERIFIED in Polynomial-Time
An edge between vertices in the same clause
An edge between complimentary vertices
- x and x' have a variable edge between them.
Term 5 of 21
What is a clause edge?
A type of punctuation used to indicate a clause
A graphical representation of all clauses in a legal contract
A boundary that separates different clauses in a document
An edge between vertices in the same clause
, Term 6 of 21
What is Euler Path Problem?
Find a CYCLE that visits each VERTEX exactly once.
-No Known Polynomial Time algorithm
An edge between complimentary vertices
- x and x' have a variable edge between them.
Same as Rudrata cycle except find a PATH.
Find a PATH that contains each EDGE exactly once.
-Can be solved in Polynomial Time
Term 7 of 21
How to prove S is an independent set?
1. Prove the problem is in NP
-Given problem and solution, Verify solution in Polynomial Time.
2. Prove problem is as hard as any NP-Complete problem. (K nown → New)
-Show reduction from known NP-Complete problem to this problem.
-Use a problem similar to this one.
-Prove forward and backward implication.
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'
-S has exactly 1 vertex per clause
-Both x₁ and x₁' are not in S.
-|S| = m = g
1. Max-Independent-Set
2. Clique
3. Vertex Cover
4. SAT
5. 3SAT
6. Independent Set