Consider how we could decide the 3COL problem: generate one…
Consider how we could decide the 3COL problem: generate one color map, and check if it is a valid coloring; if not, then reuse the space to generate a second color map, and check if it is a valid coloring; if not, then reuse the space to generate a third color map, etc, etc, until either some color map has been found valid, or all color maps have been found invalid. Observe that a color map can be generated and checked in polynomial time. What can we then say about each of the below claims (where PSPACE are the problems that can be decided in polynomial space)?