Complexity versus stability for classes of propositional formulas

DOI10.1016/S0020-0190(98)00163-XzbMath1339.03031MaRDI 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 complexity; coNP-completeness; 2CNF formulas; equivalence of formulas; Horn formulas; XOR-CNF formulas

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

03B05: Classical propositional logic

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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