  In this letter we study the NP-complete vertex cover problem on finite
connectivity random graphs. When the allowed size of the cover set is
decreased, a discontinuous transition in solvability and typical-case
complexity occurs. This transition is characterized by means of exact numerical
simulations as well as by analytical replica calculations. The replica
symmetric phase diagram is in excellent agreement with numerical findings up to
average connectivity $e$, where replica symmetry becomes locally unstable.
