The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain

DOI10.1145/3449350MaRDI QIDQ5035876zbMATH OpenOpenAlexWikidataFDO

Authors Monaldo Mastrolilli

Publication date 22 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

constraint satisfaction problemssum-of-squarestheta bodiesideal membership problemGröbner basis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Recommendations

• The complexity of the ideal membership problem for constrained problems over the Boolean domain
• scientific article; zbMATH DE number 7724189
• Ideal membership problem over 3-element CSPs with dual discriminator polymorphism
• The Complexity of the Membership Problem for Two Subclasses of Polynomial Ideals
• The ideal membership problem and polynomial identity testing

Cited in

(5)

• scientific article; zbMATH DE number 7559384 (Why is no real title available?)
• scientific article; zbMATH DE number 7724189 (Why is no real title available?)
• Error bounds for conditional algorithms in restricted complexity set membership identification
• Short proofs of ideal membership
• On the complexity of CSP-based ideal membership problems

This page was built for publication: The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain

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