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.