Computer Science 3650
Spring 2012
Solutions to Practice Questions for Quiz 7

  1. What is the definition of the class P?

    P is the class of all decision problems (or sets) that have polynomial time (deterministic) algorithms.

  2. What is the definition of the class NP?

    NP is the class of all decision problems (or sets) that have polynomial time nondeterministic algorithms.

  3. What is the definition of a polynomial time reduction from set A to set B?

    A polynomial time reduction from A to B is a function f such that

    1. f(x) is computable in polynomial time (in the length of x);
    2. for every x, x is in A if and only if f(x) is in B.

  4. What is the definition of notation A ≤p B?

    A ≤p B means that there exists a polynomial time reduction from A to B.

  5. What is the definition of an NP-complete set?

    Set A is NP-complete if

    1. A is in NP;
    2. For every set X in NP, X ≤p A.

  6. Is the satisfiability problem known to be in NP, or only conjectured to be in NP?

    The satisfiability problem is known to be in NP. There is a nondeterministic polynomial time algorithm for it.

  7. Is the satisfiability problem known to be NP-complete, or only conjectured to be NP-complete?

    The satisfiability problem is known to be NP-complete. That is the Cook/Levin theorem.

  8. Is it known whether the satisfiablity problem is in P?

    No. If P ≠ NP, then the satisfiability problem is not in P. It is conjectured, but not known, that P ≠ NP.

  9. Are there any computational problems that are neither in P nor in NP?

    Yes, there are computational problems that are not in NP (and so are not in P either). We have only mentioned that they exist, be here are some.

    The following are known not to be in NP.

    1. Given a program p and a string x that is thought of as an input to program p, determine whether running p(x) will ever stop.
    2. Given a program written in Standard ML (a programming language), is the program free from type errors?

    The following are conjectured not to be in NP. (These would be consequences of more general conjectures.)

    1. Given a clausal formula φ, is it the case that φ is not satisfiable?
    2. Given a configuration of pieces on a generalized (n×n) Checkers board, does the red player have a winning strategy from that configuration?

  10. Is it possible for a problem to be in both P and NP?

    Yes. Since P is a subset of NP, every problem in P is in both P and NP.

  11. Show that the problem of telling whether a number is composite is in NP. A number is composite if it is greater than 1 and not prime.

    We need a polynomial time nondeterministic algorithm to determine whether a number is composite.

    Input. An integer x > 1.
    Evidence. Two integers r and s.
    Check. Accept the evidence if 1 < r < x and 1 < s < x and r*s = x.

  12. The Clique problem is as follows.
    Input. An undirected graph G and a positive integer K.
    Question. Does there exist a set of K vertices in G such that, if u and v are any two of those vertices, then G has an edge from u to v?

    Show that the Clique Problem is in NP.

    We need a polynomial time nondeterministic algorithm to solve the Clique Problem.

    Input. A graph G and a positive integer K.
    Evidence. A set S of vertices of G.
    Check. Accept the evidence if S has exactly K members and, for all vertices u and v in S where u ≠ v, (u,v) is an edge in G.

  13. Let A = {x | x is an even positive integer} and B = {x | x is a positive integer that is divisible by 3}. Integers can be arbitrarily large. Give a polynomial time reduction from A to B.

    The function f(x) defined by 

       f(x) = 1  when x is odd
   f(x) = 3  when x is even
    is computable in polynomial time. Notice that, for every positive integer x (which are the only ones that make sense for these problems), x is in A if and only if f(x) is in B. That is, x is even if and only if f(x) is divisible by 3.

    Another reduction that does the job is f(x) = 3 + (x mod 2).

  14. Two graphs are isomorphic if it is possible to assign numbers to the vertices of each so that, after the numbering, the edge sets of the two graphs are identical.

    Here are two decision problems.

    The Subgraph Isomorphism Problem (SIP)
    Input. Two undirected graphs G and H.
    Question. Is H isomorphic to a subgraph of G? That is, can you get a graph that is isomorphic to H by deleting zero or more edges and zero or more vertices from G?

    The Hamilton Cycle Problem (HCP)
    Input. An undirected graph G.
    Question. Does G contain a simple cycle that includes all of its vertices? That is, can you find a cycle in G, following the edges, that includes every vertex exactly once? (Imagine doing a tour, where you start at a particular vertex, tour through the vertices (following edges), and return to the start vertex, where you are not allowed to return to a vertex that you have already visited, except the start vertex at the end of the tour.)

    Show that the HCP ≤p SIP by giving a polynomial-time reduction from HCP to SIP.

    Define f(G) = (G, Cn) where n is the number of vertices in G and Cn is a cycle of n vertices. Then f is computable in polynomial time and G has a Hamilton cycle if an only if G has a subgraph that is isomorphic to Cn. (The subgraph is the Hamilton cycle.)