6: P and NP Reductions Flashcards
What is verification?
Checking that a proposed solution to a problem is correct.
What is the prime factorisation problem? Why is it significant?
Finding the prime factors (i.e. factors that are prime numbers - have not factors themselves) of a given number. It is the basis of cryptographic systems such as RSA which assume there is no “fast” - polynomial algorithm to solve it.
What is a graph clique?
A graph is a clique of size n if it has n nodes and edges connecting each possible pairing of the n nodes.
What is a subgraph?
A graph whose nodes and edges are subsets of another parent graph.
What is a clique problem?
Finding if a graph contains a subgraph that is a clique of a certain size. Can also be verifying a certificate that this is the case for a given subgraph.
What is a satisfiability problem?
Given a logical formula, can we assign T/F values to the variables in it such that the value of the whole formula becomes true?
What is CNF? What is its structure?
Conjunctive Normal Form is a set of rules for standardising logical formulae. It compromises of literals, variables or negated variables, disjointed (ORed) in clauses, which are in turned conjoined (ANDed) together to form the whole formula.
What are SAT problems?
Satisfiability problems given in CNF format.
What does P = NP boil down to?
If there are problems that are solvable in polynomial time nondeterministically (and sometimes verifiable in polynomial time deterministically) that cannot be solved within polynomial time deterministically.
What are reductions? What are reductions aka?
Using an algorithm for one problem as a subroutine to solve another problem, especially if done to improve the time complexity of doing so, often aiming to reduce it to polynomial time. Reductions are aka transformations.
What is Cook’s Theorem?
The Cook–Levin theorem states that SAT (the Boolean Satisfiability problem) is NP-complete.
NP-completeness means that any other problem in NP can be reduced to it, so allows easier proving that other problems are in NP.
What are 3-SAT problems?
SAT Problems are satisfiability problems given in CNF format. 3-SAT problems are further restricted SAT problems such that clauses may hold no more than 3 literals. You can also define k-SAT for any such maximum number of k literals per clause.
How do you transform SAT problems to 3-SAT problems?
Split up each clause with more than 3 literals in by repeatedly taking the first 2 literals from it, and placing them in a new clause. Then add a new literal (to the whole expression) in the new clause and its negated form is added to the original clause to replace the 2 literals removed. By repeating this iteratively for each clause in the SAT problem, you can sure each clause has 3 or fewer literals in it, enforcing 3-SAT.
What are polynomial Karp reductions?
Karp reductions change a problem into an instance of another one within polynomial time.
What are polynomial Turing/Cook reductions?
Turing reductions use one problem as a subroutine ( ~ oracle) to solve another one, being called at most a polynomial amount of times.
What is the difference between Karp and Turing/Cook polynomial reductions?
Cook/Turing reductions relate the computability of problems (i.e. if A is computable [in polynomial time] then so is B), whereas Karp reductions are more about relating the fundamental structure of problems (i.e. Problem A can be “presented” as a case of Problem B).
Karp reductions change a problem into an instance of another one and Turing reductions use one problem as a subroutine (~ oracle) to solve another one, being called at most a polynomial amount of times.
How do you prove a problem is in P?
Provide a proof that it is deterministically solvable within polynomial time - usually just an algorithm to do so.
How do you prove a problem is in NP?
Provide a proof that it is nondeterministically solvable within polynomial time - a certificate to get precomputed output that must, in turn, be checkable within polynomial time.
How do you prove a problem is in NP-complete?
Prove that the problem is in NP, and then that any problem in NP can be reduced/transformed to it (in practice only need to show 1 problem can be transformed into it since, in turn, all others must be able to transform into that 1 problem).
How do you prove a problem is in NP-hard?
Show a problem is in both NP and NP-complete.
What does the Cook-Levin theorem state? What is its significance?
SAT is NP-complete. SAT was the first problem proven to be NP-complete, and seeing if it can be reduced to other problems the allowed for easy checking if other problems are also NP-complete.
