On problems with short certificates

DOI10.1007/BF01178668zbMath0818.68075MaRDI QIDQ1338895

Graham E. Farr

Publication date: 17 August 1995

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

forcinggraph colouringHamiltonian circuitsBoolean satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

The inapproximability of non-NP-hard optimization problems.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• Complete problems for deterministic polynomial time
• Bandwidth contrained NP-complete problems
• Classes of bounded nondeterminism
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
• On the Structure of Polynomial Time Reducibility
• The Planar Hamiltonian Circuit Problem is NP-Complete
• A Computing Procedure for Quantification Theory
• The complexity of theorem-proving procedures

This page was built for publication: On problems with short certificates