On the complexity of Hilbert refutations for partition
From MaRDI portal
Publication:2252121
DOI10.1016/j.jsc.2013.06.005zbMath1357.68087arXiv1208.3346OpenAlexW2147951657WikidataQ56859904 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
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Decidability (number-theoretic aspects) (11U05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On probabilistic algorithm for solving almost all instances of the set partition problem, Generalization of the subset sum problem and cubic forms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
