Complexity Classes Flashcards
(18 cards)
What is a CNF?
Conjunctive Normal Form, or a conjunction of disjunctions
What is a K-CNF?
A boolean formula with n boolean variables (literals) in conjunction with K disjunctions
If there are 2^K clauses made up of variations of the same K literals, what can be said about the K-CNF?
It is unsatisfiable
For a K-CNF with n variables, how many possible assignments are there?
2^n
What are the four main complexity classes?
P, NP, NP-Complete, and NP-Hard
What is P complexity?
Problems that are solvable in polynomial time
What is NP complexity?
Problems that can be verified in polynomial time, but might not be solvable in that much time
What is NP-Complete?
A solution is verifiable in polynomial time, but you may need to go through all 2^n assignments
What is NP-Hard?
Not necessarily in NP time, but at least as hard as a problem in NPC time
What is K-CNFSAT?
Given a K-CNF, determine whether there is an assignment of variables that makes it true
What is the complexity class of K-CNFSAT when K is 2?
P, Polynomial
What is the complexity class of K-CNFSAT when K is 3?
NP, Nondeterministically Polynomial
What is the complexity class of K-CNF?
P, Polynomial
How do you prove that a problem is NP-Complete?
Prove that it is in NP, and check if it is in NPH
How do you prove if something is in NP?
Check if the problem is solvable in P time
How do you check if something is in NPH?
Reduce a known NPC problem to this unknown one, and prove it is solvable in P time
What can you reduce to K-Clique that can prove that it’s verifiable in NPC?
Reduce 3-CNF with K clauses to K-Clique
1. Create vertex for each variable in clause
2. Connect each non-negating vertex in different clauses
3. If there is a clique, then 3-CNF is satisfiable, and K-Clique is NPH
What can you reduce to Independent Set that can prove that it’s verifiable in NPC?
Reduce K-Clique to Independent Set
There is a K-Clique in G if and only if it is an Independent set in G’ and vice versa
