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