The power of primitive positive definitions with polynomially many variables
DOI10.1093/LOGCOM/EXW005zbMATH Open1387.08001OpenAlexW2324696293MaRDI QIDQ3133171FDOQ3133171
Authors: Victor Lagerkvist, Magnus Wahlström 
Publication date: 13 February 2018
Published in: Journal Of Logic And Computation (Search for Journal in Brave)
Full work available at URL: http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-139605
Recommendations
- Positive existential definability of multiplication from addition and the range of a polynomial
- Positive versions of polynomial time
- On the expression complexity of equivalence and isomorphism of primitive positive formulas
- Bounds and definability in polynomial rings
- On the strength of uniqueness quantification in primitive positive formulas
- On the number of sets definable by polynomials
- scientific article; zbMATH DE number 426121
- scientific article; zbMATH DE number 4148233
- scientific article; zbMATH DE number 3884129
- scientific article; zbMATH DE number 1428941
constraint satisfaction problemsco-clonepolynomially closed co-cloneprimitive positive definitionssuperpolynomially closed co-clone
Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70)
Cited In (12)
- The number of clones determined by disjunctions of unary relations
- Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
- Title not available (Why is that?)
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Sparsification lower bounds for list \(H\)-coloring
- Positive primitive structures
- A dichotomy theorem for the inverse satisfiability problem
- Title not available (Why is that?)
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- Best-case and worst-case sparsifiability of Boolean CSPs
- Finitely Many Primitive Positive Clones
- Best-case and worst-case sparsifiability of Boolean CSPs
This page was built for publication: The power of primitive positive definitions with polynomially many variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133171)
