CSCI 4602
Fall 2016
Practice Questions for Quiz 6

Answers are to come.

1. Is the following formula satisfiable?

   (x ∨ y ∨ z) ∧ (¬x ∨ ¬y) ∧ (¬x ∨ ¬z) ∧ (¬y ∨ ¬z)

   Answer

2. What conjecture needs to be proved in order to conclude that there is no polynomial time algorithm to solve the clique problem?

   Answer

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

   Answer

4. What is the definition of the class NP?

   Answer

5. Give an example of a language that is known not to be NP-complete.

   Answer

6. Suppose that language A is in NP. Can you conclude, from just that information, that A is not in P?

   Answer

7. What is the definition of a polynomial-time mapping reduction from A to B?

   Answer

8. Is SAT known to be NP-complete or only conjectured to be NP-complete?

   Answer

9. Suppose that a polynomial-time algorithm is found for the Vertex Cover Problem. Would that discovery imply that P = NP?

   Answer

10. Describe the error in the following fallacious "proof" that P is different from NP.

    A propositional formula of length n can have at least sqrt(n) different variables. It is satisfiable if some assignment of values to those variables makes it true. But there are 2^sqrt(n) assignments of values to the variables, and trying them all takes at least 2^sqrt(n) steps. Since 2^sqrt(n) grows faster than any polynomial, SAT is not solvable in polynomial time. So SAT is not in P. But SAT is in NP, so P and NP are clearly different classes.

    (This argument has actually been proposed before. The first recorded instance was by a group of Russian mathematicians in 1959; they quickly realized their error.)

    Answer

11. Two undirected graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂), are isomorphic if there exists a bijection f: V₁ → V₂ so that,

     (∀u, v ∈ V₁) ((u,v) ∈ E₁ ⇔ (f (u), f (v)) ∈ E₂).

    (In simpler terms, G₁ and G₂ are isomorphic if it is possible to renumber the vertices of one of them so that it is identical to the other one.)

    The Subgraph Isomorphism Problem (SIP) is as follows.

    Input. Two undirected graphs G and H.

    Question. Is H isomorphic to a subgraph of G? That is, can you remove zero or more vertices and zero or more edges from G and obtain a graph that has the same structure as H?

    1. Show that SIP is in NP.

       Answer

    2. Show that the Clique Problem polynomial-time reduces to SIP.

       Answer

12. The Subset Sum Problem (SSP) is the following decision problem.

    Input. A list (x₁, x₂, … x_n) and a positive integer K.

    Question. Does there exist an index set I ⊆ {1, 2, …, n} such that (Σ_{i ∈ I} x_i) = K?

    The Partition Problem (PP) is the following decision problem.

    Input. A list (x₁, x₂, …, x_n).

    Question. Does there exist an index set I ⊆ {1, 2, …, n} such that (Σ_{i ∈ I} x_i) = (Σ_{i ∉ I} x_i)?

    1. Show that PP ∈ NP.

       Answer

    2. Show that PP ≤_p SSP.

       Answer

13. Does there exist a polynomial-time mapping reduction from the Subgraph Isomorphism Problem to the Clique Problem? Why or why not?

    Answer

14. Suppose that a particular program p takes O(n) time to compute f(n) for some function f, where n is an integer written in base 10. Is p a polynomial-time algorithm?

    Answer