ON PROBLEMS WITH SHORT CERTIFICATES

We consider languages in NP whose certificate size is bounded by a fix ed, slowly growing function (say f(n)) of the input size. The classes f(n)-NP, which are related to classes of Kintala and Fischer, are defi ned in order to classify such languages. We show that several natural problems, involving Boolean satisfiability, graph colouring and Hamilt onian circuits, are complete for f(n)-NP. Each of our problems is obta ined by taking a known NP-complete problem and introducing an ingredie nt we call forcing, whereby a partial structure is enlarged by a seque nce of local improvements. As special cases of these results we obtain some new logspace completeness results for P.