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...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2014
|
| _version_ | 1826268559929507840 |
|---|---|
| author | Margulies, S Onn, S Pasechnik, D |
| author_facet | Margulies, S Onn, S Pasechnik, D |
| author_sort | Margulies, S |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T21:11:33Z |
| format | Journal article |
| id | oxford-uuid:3e58d237-3ae9-4e69-9e4a-8ea6c21d2bd8 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T21:11:33Z |
| publishDate | 2014 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:3e58d237-3ae9-4e69-9e4a-8ea6c21d2bd82022-03-26T14:25:01ZOn the complexity of Hilbert refutations for partitionJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:3e58d237-3ae9-4e69-9e4a-8ea6c21d2bd8EnglishORA DepositElsevier2014Margulies, SOnn, SPasechnik, DGiven 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. |
| spellingShingle | Margulies, S Onn, S Pasechnik, D On the complexity of Hilbert refutations for partition |
| title | On the complexity of Hilbert refutations for partition |
| title_full | On the complexity of Hilbert refutations for partition |
| title_fullStr | On the complexity of Hilbert refutations for partition |
| title_full_unstemmed | On the complexity of Hilbert refutations for partition |
| title_short | On the complexity of Hilbert refutations for partition |
| title_sort | on the complexity of hilbert refutations for partition |
| work_keys_str_mv | AT marguliess onthecomplexityofhilbertrefutationsforpartition AT onns onthecomplexityofhilbertrefutationsforpartition AT pasechnikd onthecomplexityofhilbertrefutationsforpartition |