On problems with short certificates (Q1338895)

We consider languages in NP whose certificate size is bounded by a fixed, 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 defined in order to classify such languages. We show that several natural problems, involving Boolean satisfiability, graph colouring and Hamiltonian circuits, are complete for \(f(n)\)-NP. Each of our problems is obtained by taking a known NP-complete problem and introducing an ingredient we call forcing, whereby a partial structure is enlarged by a sequence of local improvements. As special cases of these results we obtain some new logspace completeness results for P.