A dichotomy theorem for the inverse satisfiability problem

DOI10.4230/LIPICS.FSTTCS.2017.39MaRDI QIDQ5136331zbMATH OpenOpenAlexFDO

Authors Victor Lagerkvist, Biman Roy

Publication date 25 November 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/8374/pdf/LIPIcs-FSTTCS-2017-39.pdf/

zbMATH Keywords

universal algebraclone theorysatisfiability problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)

Recommendations

• Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
• The Inverse Satisfiability Problem
• The complexity of minimal satisfiability problems
• A dichotomy theorem for maximum generalized satisfiability problems.
• A preliminary investigation of satisfiability problems not harder than 1-in-3-SAT

Cites work

• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Closed systems of functions and predicates
• Constructing NP-intermediate problems by blowing holes with parameters of various properties
• Decidability of definability
• Enumerating All Solutions for Constraint Satisfaction Problems
• Inverse NP problems
• On generating all solutions of generalized satisfiability problems
• On the Structure of Polynomial Time Reducibility
• Partial Polymorphisms and Constraint Satisfaction Problems
• Strong partial clones and the time complexity of SAT problems
• Structure identification of Boolean relations and plain bases for co-clones
• The Inverse Satisfiability Problem
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The algebras of partial functions and their invariants
• The complexity of satisfiability problems
• The power of primitive positive definitions with polynomially many variables
• Weak bases of Boolean co-clones

Cited in

(6)

• Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
• Algebraic global gadgetry for surjective constraint satisfaction
• The inverse satisfiability problem
• The inverse plurality rule-an axiomatization
• scientific article; zbMATH DE number 7561680 (Why is no real title available?)
• The Complexity of Satisfaction Problems in Reverse Mathematics

This page was built for publication: A dichotomy theorem for the inverse satisfiability problem

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