Complexity versus stability for classes of propositional formulas

DOI10.1016/S0020-0190(98)00163-XzbMATH Open1339.03031OpenAlexW1973612331MaRDI QIDQ293437FDOQ293437

Authors: 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

Recommendations

• Mathematical Foundations of Computer Science 2003
• The Complexity of Very Simple Boolean Formulas with Applications
• On the restricted equivalence for subclasses of propositional logic
• scientific article; zbMATH DE number 3978379
• The complexity of satisfiability problems

zbMATH Keywords

computational complexity2CNF formulascoNP-completenessequivalence of formulasHorn formulasXOR-CNF formulas

Mathematics Subject Classification ID

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

Cites Work

• The complexity of computing the permanent
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The complexity of satisfiability problems
• Complexity of generalized satisfiability counting problems
• Title not available (Why is that?)
• On the complexity of the maximum satisfiability problem for Horn formulas
• On sentences which are true of direct unions of algebras
• Existence of simple propositional formulas
• A dichotomy theorem for maximum generalized satisfiability problems.

Cited In (5)

• Propositional truth maintenance systems: Classification and complexity analysis
• Title not available (Why is that?)
• Mathematical Foundations of Computer Science 2003
• Satisfiable formulas closed under replacement
• Probability logic and optimization SAT: The PSAT and CPA models

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

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