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...
Príomhchruthaitheoirí: | , , |
---|---|
Formáid: | Journal article |
Teanga: | English |
Foilsithe / Cruthaithe: |
Elsevier
2014
|