Computer Science 4602, Fall 2019
Assignment 5

1. What is the definition of class NP?

2. What is the definition of an NP-complete problem?

3. Let A be the set of all natural numbers that are prime. Does there exist a polynomial-time mapping reduction from A to SAT?

4. Give an example of a language that is not in NP.

5. Is SAT known to be NP-complete, or is SAT only conjectured to be NP-complete?

6. Is it known that SAT ∉ P?

7. 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.

8. 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.)