On the strength of uniqueness quantification in primitive positive formulas

DOI10.4230/LIPICS.MFCS.2019.36MaRDI QIDQ5092397zbMATH OpenFDO

Authors Victor Lagerkvist, Gustav Nordh

Publication date 21 July 2022

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

zbMATH Keywords

constraint satisfaction problemsclone theoryprimitive positive definitions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• scientific article; zbMATH DE number 1390075
• On the unique satisfiability problem
• The complexity of problems for quantified constraints
• The unique Horn-satisfiability problem and quadratic Boolean equations.
• Constraint satisfaction with counting quantifiers. II

Cites work

• scientific article; zbMATH DE number 1390075 (Why is no real title available?)
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• A dichotomy theorem for the inverse satisfiability problem
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Closed systems of functions and predicates
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of generalized satisfiability counting problems
• Function Algebras on Finite Sets
• On the algebraic structure of combinatorial problems
• On the complexity of \(k\)-SAT
• On the unique satisfiability problem
• Partial Polymorphisms and Constraint Satisfaction 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 facets (and some facets of complexity)
• Weak bases of Boolean co-clones

Cited in

(2)

• The power of primitive positive definitions with polynomially many variables
• On the Strength of Uniqueness Quantification in Primitive Positive Formulas

This page was built for publication: On the strength of uniqueness quantification in primitive positive formulas

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