(2+\(f\)(\(n\)))-SAT and its properties.

DOI10.1016/S0166-218X(03)00194-XzbMath1159.68467OpenAlexW2092963377MaRDI QIDQ1421480

D. Massart

Publication date: 26 January 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00194-x

zbMATH Keywords

Computational complexitySATExponential-time hypothesis

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Computational complexity of some restricted instances of 3-SAT ⋮ Computational complexity of quantified Boolean formulas with fixed maximal deficiency

Cites Work

• Unnamed Item
• Unnamed Item
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Resettable zero-knowledge (extended abstract)
• On the Structure of Polynomial Time Reducibility
• Tricritical points in random combinatorics: the -SAT case
• Determining computational complexity from characteristic ‘phase transitions’
• Zaps and Their Applications
• On the complexity of \(k\)-SAT

This page was built for publication: (2+\(f\)(\(n\)))-SAT and its properties.