Optimal satisfiability for propositional calculi and constraint satisfaction problems.

DOI10.1016/S0890-5401(03)00092-0zbMath1058.68062MaRDI QIDQ1426002

Steffen Reith, Heribert Vollmer

Publication date: 14 March 2004

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

\(s\)-formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (4)

Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ Generalized modal satisfiability ⋮ The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy theorem for maximum generalized satisfiability problems.
• The complexity of optimization problems
• More complicated questions about maxima and minima, and some closures of NP
• Generalizations of Opt P to the polynomial hierarchy
• Complexity classes of optimization functions
• Complexity of generalized satisfiability counting problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Satisfiability problems for propositional calculi
• On the Structure of Polynomial Time Reducibility
• On generating all solutions of generalized satisfiability problems
• The complexity of satisfiability problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

This page was built for publication: Optimal satisfiability for propositional calculi and constraint satisfaction problems.