On problems with short certificates (Q1338895)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On problems with short certificates |
scientific article |
Statements
On problems with short certificates (English)
0 references
17 August 1995
0 references
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.
0 references
Boolean satisfiability
0 references
graph colouring
0 references
Hamiltonian circuits
0 references
forcing
0 references