On the complexity of Hilbert refutations for partition

DOI10.1016/j.jsc.2013.06.005zbMath1357.68087arXiv1208.3346WikidataQ56859904 ScholiaQ56859904MaRDI QIDQ2252121

Shmuel Onn, Susan Margulies, Dimitrii 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

partition; linear algebra; Hilbert's Nullstellensatz

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

11U05: Decidability (number-theoretic aspects)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Generalization of the subset sum problem and cubic forms, On probabilistic algorithm for solving almost all instances of the set partition problem

Cites Work

• Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
• Nowhere-zero flow polynomials
• Colorings and orientations of graphs
• Lower bounds for the polynomial calculus
• Stable sets and polynomials
• The origin of representation theory
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
• Combinatorial Nullstellensatz
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• Complexity of Positivstellensatz proofs for the knapsack
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item