On the complexity of Hilbert refutations for partition

DOI10.1016/J.JSC.2013.06.005MaRDI QIDQ2252121zbMATH OpenOpenAlexWikidataFDO

Authors Susan Margulies, Shmuel Onn, Dmitrii V. Pasechnik

Publication date 16 July 2014

Published in Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

partitionlinear algebraHilbert's Nullstellensatz

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Decidability (number-theoretic aspects) (11U05)

Abstract: Given a set of integers W, the Partition problem determines whether W can be divided into two disjoint subsets with equal sums. We model the Partition problem as a system of polynomial equations, and then investigate the complexity of a Hilbert's Nullstellensatz refutation, or certificate, that a given set of integers is not partitionable. We provide an explicit construction of a minimum-degree certificate, and then demonstrate that the Partition problem is equivalent to the determinant of a carefully constructed matrix called the partition matrix. In particular, we show that the determinant of the partition matrix is a polynomial that factors into an iteration over all possible partitions of W.

Recommendations

• Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
• Some efficiently solvable problems over integer partition polytopes
• Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 1405441

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256733 (Why is no real title available?)
• scientific article; zbMATH DE number 1916823 (Why is no real title available?)
• scientific article; zbMATH DE number 3336895 (Why is no real title available?)
• Colorings and orientations of graphs
• Combinatorial Nullstellensatz
• Complexity of Positivstellensatz proofs for the knapsack
• Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
• Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• Lower bounds for the polynomial calculus
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• Nowhere-zero flow polynomials
• Stable sets and polynomials
• The origin of representation theory

Cited in

(3)

• A comment on \('NP=P?'\) and restricted partitions
• On probabilistic algorithm for solving almost all instances of the set partition problem
• Generalization of the subset sum problem and cubic forms

This page was built for publication: On the complexity of Hilbert refutations for partition

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