Journal article
On the complexity of Hilbert refutations for partition
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 457.2KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.jsc.2013.06.005
Authors
- Publisher:
- Elsevier
- Journal:
- Journal of Symbolic Computation More from this journal
- Volume:
- 66
- Pages:
- 70–83
- Publication date:
- 2014-02-14
- Acceptance date:
- 2013-06-21
- DOI:
- ISSN:
-
0747-7171
- Language:
-
English
- Keywords:
- UUID:
-
uuid:3e58d237-3ae9-4e69-9e4a-8ea6c21d2bd8
- Deposit date:
-
2015-11-07
Terms of use
- Copyright holder:
- Margulies et al.
- Copyright date:
- 2015
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Elsevier at https://doi.org/10.1016/j.jsc.2013.06.005
If you are the owner of this record, you can report an update to it here: Report update to this record