On problems with short certificates
type: Item
instance of: scholarly article
title: On problems with short certificates
zbMATH Open document ID: 0818.68075
DOI: 10.1007/BF01178668
published in: Acta Informatica
publication date: 1995-08-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 695003
zbMATH Keywords: Boolean satisfiability
zbMATH Keywords: graph colouring
zbMATH Keywords: Hamiltonian circuits
zbMATH Keywords: forcing
author: Graham Farr
MaRDI profile type: Publication
cites work: The complexity of theorem-proving procedures
cites work: A Computing Procedure for Quantification Theory
cites work: Classes of bounded nondeterminism
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: Complete problems for deterministic polynomial time
cites work: Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
cites work: On the Structure of Polynomial Time Reducibility
cites work: Q3740256
cites work: Bandwidth contrained NP-complete problems
cites work: Q4739657
cites work: Q5573961
Recommended article: Certificate transparency with enhancements and short proofs
Recommended article: Q5196806
Recommended article: Breaking the short certificateless signature scheme
Recommended article: Q4434881
Recommended article: Efficient and Short Certificateless Signature
Recommended article: A new provably secure certificateless short signature scheme
Recommended article: Short Signatures from Weaker Assumptions
Recommended article: Short certificates for tournaments
Recommended article: Q4448398
description: scientific article; zbMATH DE number 695003