Complexity versus stability for classes of propositional formulas

DOI10.1016/S0020-0190(98)00163-XzbMath1339.03031OpenAlexW1973612331MaRDI QIDQ293437

Nadia Creignou

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S002001909800163X?np=y

zbMATH Keywords

computational complexitycoNP-completeness2CNF formulasequivalence of formulasHorn formulasXOR-CNF formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Probability logic and optimization SAT: The PSAT and CPA models

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• Existence of simple propositional formulas
• A dichotomy theorem for maximum generalized satisfiability problems.
• On the complexity of the maximum satisfiability problem for Horn formulas
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Complexity of generalized satisfiability counting problems
• The complexity of satisfiability problems
• On sentences which are true of direct unions of algebras

This page was built for publication: Complexity versus stability for classes of propositional formulas