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...
| Autores principales: | , , |
|---|---|
| Formato: | Journal article |
| Publicado: |
2015
|
| _version_ | 1826291818073948160 |
|---|---|
| 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. © 2014. |
| first_indexed | 2024-03-07T03:05:10Z |
| format | Journal article |
| id | oxford-uuid:b23f1530-57a2-4ccc-94d2-857c34b1e445 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:05:10Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | oxford-uuid:b23f1530-57a2-4ccc-94d2-857c34b1e4452022-03-27T04:10:27ZOn the complexity of Hilbert refutations for partitionJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:b23f1530-57a2-4ccc-94d2-857c34b1e445Symplectic Elements at Oxford2015Margulies, 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. © 2014. |
| 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 |