Assigned: | Monday, November 11 |
Due: | Monday, November 18 |
What is the definition of class NP?
What is the definition of an NP-complete problem?
Let A be the set of all natural numbers that are prime. Does there exist a polynomial-time mapping reduction from A to SAT?
Give an example of a language that is not in NP.
Is SAT known to be NP-complete, or is SAT only conjectured to be NP-complete?
Is it known that SAT ∉ P?
Let DOUBLE-SAT be the problem about propositional formulas φ in 3-CNF form of determining whether φ has at least two different satisfying truth-value assignments. Prove that DOUBLE-SAT is NP-complete.
See exercise set 4 for the definition of isomorphic graphs.
Suppose that G and H are simple graphs. Say that H is isomorphic to a subgraph of G provided it is possible to remove zero or more vertices and zero or more edges from G and get a graph that is isomorphic to H. (When you remove a vertex v, you must also remove all edges that are incident on v.)
Let SUBISO = {(G, H) | H is isomorphic to a subgraph of G}. Prove that SUBISO is NP-complete.
(Hint. Reduce from the Clique Problem.)