Homework 3

Problem 1.

Suppose I give you a subroutine that can answer the decision problem for \(k\)-Coloring: Given a graph \(G\), it tells you if the graph can be colored with \(k\) colors. (It does not tell you anything else.)

Show how to use this subroutine to find a \(k\)-coloring of a graph. You are allowed to call the subroutine a polynomial number of times (on graphs of polynomial size).

Bonus problem: Do the same for Planar3Coloring. (That is, I give you a subroutine that decides if a planar graph can be 3-colored, and you want to compute a 3-coloring of a planar graph.)

Problem 2.

Let \(A(x)\) be a property that is true if and only if there is a witness \(w\) of length \(|w| \leq \log n\) such that \(B(x,w)\) is true, where \(B(x,w)\) can be decided in polynomial time.

Show that \(A(x)\) can be decided in polynomial time.

Problem 3.

Consider the following decision problem SmallFactor: Given two integers \(q\) and \(r\), does \(q\) have a factor smaller than \(r\)?

Show that SmallFactor is in \(NP \cap coNP\). You can use the fact that Primality is in NP.