Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem

DOI10.1016/j.jcss.2020.10.004zbMath1477.68127OpenAlexW3102682405MaRDI QIDQ2221799

Victor Lagerkvist, Biman Roy

Publication date: 2 February 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2020.10.004

zbMATH Keywords

inverse problemsconstraint satisfaction problemsuniversal algebrasatisfiability problemsclone theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)

Related Items (1)

Computational Short Cuts in Infinite Domain Constraint Satisfaction

Cites Work

• Unnamed Item
• Unnamed Item
• 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 CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
• The power of primitive positive definitions with polynomially many variables
• 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
• Function Algebras on Finite Sets
• 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: Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem