Suppose I give you a subroutine that can answer the decision problem
-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.)
be a property that is true if and only if there is a
of length \(|w| \leq \log n\)
such that \(B(x,w)\)
can be decided in polynomial time.
Show that \(A(x)\) can be decided in polynomial time.
Consider the following decision problem SmallFactor
: Given two
, 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.