scientific article; zbMATH DE number 169728

MaRDI QIDQ4038402zbMATH OpenFDO

Authors Francisco Antonio Doria, N. C. A. da Costa

Publication date 16 May 1993

zbMATH Keywords

Boolean formulasexponential timeKolmogorov complexitynormal formssatisfiability

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• The complexity of satisfiability problems
• The Complexity of Very Simple Boolean Formulas with Applications
• Generating hard satisfiability problems
• scientific article; zbMATH DE number 1113991
• On the complexity of k-SAT

Cited in

(6)

• Generic hardness of the Boolean satisfiability problem
• The opacity of backbones
• The Complexity of Very Simple Boolean Formulas with Applications
• On the structure of Boolean satisfiability
• scientific article; zbMATH DE number 496040 (Why is no real title available?)
• scientific article; zbMATH DE number 7378390 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4038402)