Subset sum problem: Difference between revisions

Revision as of 19:53, 29 July 2025

Latest revision as of 19:53, 8 August 2025

Line 31:

*The input integers are positive, and ''T'' = sum(''S'')/2. This can also be proved by reduction from the general variant; see [[partition problem]].

The analogous counting problem #SSP, which asks to enumerate the number of subsets summing to the target, is [[Sharp P complete|#P-complete]].<ref>[[Yuval Filmus|Filmus, Yuval]] (30 January 2016). [https://cs.stackexchange.com/a/52466 Answer] to: "[https://cs.stackexchange.com/q/52453 Is there a known, fast algorithm for counting all subsets that sum to below a certain number?]". ''Theoretical Computer Science [[Stack Exchange]].'' Note that Filmus' citation in support of the claim (Faliszewski, Piotr; Hemaspaandra, Lane (2009). "The complexity of power-index comparison". ''Theoretical Computer Science''. Elsevier. '''410''': 101-107. DOI&nbsp;[http://dx.doi.org/10.1016/j.tcs.2008.09.034 10.1016/j.tcs.2008.09.034]) does not in fact prove the claim, instead directing readers to another citation ([[Christos Papadimitriou|Papadimitriou, Christos]] (1994). [[iarchive:computationalcom0000papa/|''Computational Complexity'']]. Addison-Wesley: Reading, MA. Chapter&nbsp;9. {{ISBN|0-201-53082-1}}&nbsp;&#x2014;— via the [[Internet Archive]]), which does not explicitly prove the claim either. Papadimitriou's proof that SSP is NP-complete via reduction of [[3SAT]] does, however, generalize to a reduction from [[Sharp-SAT|#3SAT]] to #SSP.</ref>

== Exponential time algorithms ==