A Dichotomy Theorem for the Inverse Satisfiability Problem
From MaRDI portal
Publication:5136331
DOI10.4230/LIPICS.FSTTCS.2017.39zbMATH Open1491.68089OpenAlexW2788734544MaRDI QIDQ5136331FDOQ5136331
Publication date: 25 November 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8374/pdf/LIPIcs-FSTTCS-2017-39.pdf/
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)
Cites Work
- On the Structure of Polynomial Time Reducibility
- The complexity of satisfiability problems
- The algebras of partial functions and their invariants
- On generating all solutions of generalized satisfiability problems
- Decidability of Definability
- Closed systems of functions and predicates
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- Structure identification of Boolean relations and plain bases for co-clones
- The Inverse Satisfiability Problem
- Weak bases of Boolean co-clones
- Strong partial clones and the time complexity of SAT problems
- Enumerating All Solutions for Constraint Satisfaction Problems
- Partial Polymorphisms and Constraint Satisfaction Problems
- The power of primitive positive definitions with polynomially many variables
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Inverse NP problems
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
Cited In (4)
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)
