scientific article; zbMATH DE number 6970794

DOI10.23638/LMCS-14(4:10)2018MaRDI QIDQ4553280zbMATH OpenFDO

Authors Nadia Creignou, Reinhard Pichler, Stefan Woltran

Publication date 2 November 2018

Full work available at URL https://arxiv.org/abs/1711.07786

Mathematics Subject Classification ID

Classical propositional logic (03B05) Logic in computer science (03B70) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Further improvements for SAT in terms of formula length
• SAT vs. search for qualitative temporal reasoning
• scientific article; zbMATH DE number 1954175
• Decomposing SAT problems into connected components
• A complexity analysis of the SAT problem
• Theory and Applications of Satisfiability Testing
• The complexity of the satisfiability problem for Krom formulas

Cites work

• A Complete Classification of the Complexity of Propositional Abduction
• A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
• Bases for Boolean co-clones
• Belief revision and update: Complexity of model checking
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Closed systems of functions and predicates
• Counting complexity of propositional abduction
• Generalizations of Opt P to the polynomial hierarchy
• scientific article; zbMATH DE number 4060725 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 809154 (Why is no real title available?)
• scientific article; zbMATH DE number 3325539 (Why is no real title available?)
• On the algebraic structure of combinatorial problems
• On the complexity of propositional knowledge base revision, updates, and counterfactuals
• Partial Polymorphisms and Constraint Satisfaction Problems
• The complexity class θp2: Recent results and applications in AI and modal logic
• The complexity of logic-based abduction
• The complexity of optimization problems
• The complexity of satisfiability problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• What makes propositional abduction tractable

Cited in

(2)

• An extension-based approach to belief revision in abstract argumentation
• Choice logics and their computational properties

This page was built for publication:

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