On the complexity of Hilbert refutations for partition

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of symbolic computation 2015-01, Vol.66, p.70-83
Main Authors: Margulies, S., Onn, S., Pasechnik, D.V.
Format: Article
Language:English
Subjects:
Hilbert's Nullstellensatz
Linear algebra
Partition
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0747-7171
1095-855X
DOI:10.1016/j.jsc.2013.06.005