A Dichotomy Theorem for the Inverse Satisfiability Problem

DOI10.4230/LIPIcs.FSTTCS.2017.39zbMath1491.68089OpenAlexW2788734544MaRDI QIDQ5136331

Biman Roy, Victor Lagerkvist

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 algebrasatisfiability problemsclone theory

Mathematics Subject Classification ID

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

Related Items (1)

Unnamed Item

Cites Work

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

This page was built for publication: A Dichotomy Theorem for the Inverse Satisfiability Problem