Problem 9 - Complexity Classes

1.

Describe the inclusion relation among the complexity classes $P$, $NP$ and $NSPACE$.

2.

Describe a method of proving the $NP$-completeness of a problem which is contained in $NP$.

3.

Using the $NP$-completeness of the satisfiability problem of a logical formula, show that the problem of determining the satisfiability of a CNF formula such that each clause contains at most three literals is $NP$-complete.

See [HOP79] for a detailed answer.