Solving Subset Sum Without Concentration: NP-Completeness & Exponential Time Hypothesis
Explore the complexities of solving Subset Sum problem without concentration through the lens of NP-completeness and Exponential Time Hypothesis, revealing the challenges and implications in computational complexity theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Solving Subset Sum in the absence of concentration Joint work with Per Austrin, Petteri Kaski and Mikko Koivisto. Jesper Nederlof Technical University Eindhoven
Elephant in room: NP-completeness SETH (Strong ETH) We are here ETH (Exponential Time Hypothesis) P NP
Timeline of this talk Our contribution context Concluding remarks Joux et al. approach
Subset Sum Given integers ?1, ,??,? Find S {1, ,?} such that a S = ? ???= ?. Our goal: solve fast in the worst case. ?(??)time (Bellman (60 s)) ?(2?/2) time (Horowitz-Sahni (70 s)) Not in polynomial time unless ? = ?? Not in 2?(?) time unless the ETH fails.
Subset Sum Given integers ?1, ,??,? Find S {1, ,?} such that a S = ? ???= ?. Our goal: solve fast in the worst case. ?(??)time (Bellman (60 s)) ?(2?/2) time (Horowitz-Sahni (70 s)) Not in polynomial time unless ? = ?? Not in 2?(?) time unless the ETH fails.
Horowitz-Sahni (70s) ?1, ,??/2, ??/2+1, ,??, t
Horowitz-Sahni (70s) ?1, ,??/2, ??/2+1, ,??, t ? ? Expand all subsets and store sum {? ? :? [?/2]} {? ? :? {?/2 + 1, ,?} j ? 2?/2 time Sort and Eliminate duplicates ?1,?2, ,?? 1,?|?| ?1,?2, ,?? 1,?|?| If ??+ ??< ? -> increase i, If ??+ ??> ? -> decrease j, If ??+ ??= ? -> solution Declare NO if i or j out of range Linear Search i
Average Case Subset Sum Density: ?/lg?????? Random instance of density d: All integers are picked uniformly from [2?/?] Density 1 is the hardest to solve in PTIME (Impagliazzo & Naor( 96)). Density at most .96: reduce to shortest vector problem (Coster et al.( 92)) Joux et al.( 10): O(2.337?) time for density 1 Improved to ? 2.291?by Becker et al. ( 11)
Our contribution There is a Monte Carlo algorithm solving subset sum in ? 2.3399??4 time. B is the maximum number of times an integer arises as sum of subsets of [n], i.e. ? = ????|? 1(?)|. For (?1, ,??) = (0,1,2,4,8 ), B=1 For (?1, ,??) = (0,0,0,0,0 ), B=2? B is small for random instances with low density. Obtained by analyzing a variant of the algorithm of Joux et al.
Joux et al.10 algorithm Assume ? = ?/2 for simplicity. Na ve algorithm: Take prime ? 2?/2, ?? ? uniformly at random. Enumerate ? = {? ?/4:?(?) ???}. Using Linear Search! [?] [?] ?/4:?(?) ?? ??}. Enumerate ? = {? Iterate over all ?,? ? ?s.t. a(L)+a(R)=t. Return YES if you encounter a disjoint pair. ? ? ?/4?= O(2.8113??) time. Takes ?/4+
The subsets L of S generate about 2?/2 sums Joux et al. 10 algorithm (a lot!). So we can guess a(L) modulo 2?/2 and reconstruct S via this subset! Assume ? = ?/2 for simplicity. Na ve algorithm: Joux et al. algorithm: Take prime ? 2?/2, ?? ? uniformly at random. Enumerate ? = {? ?/4:?(?) ???}. [?] [?] ?/4:?(?) ?? ??}. Enumerate ? = {? Iterate over all ?,? ? ?s.t. a(L)+a(R)=t. Return YES if you encounter a disjoint pair. ? ? ?/4?= O(2.8113??) time. Takes ?/4+
The subsets L of S generate about 2?/2 sums Joux et al. 10 algorithm (a lot!). So we can guess a(L) modulo 2?/2 and reconstruct S via this subset! Assume ? = ?/2 for simplicity. Na ve algorithm: Joux et al. algorithm: Take ? 2?/2, ?? ? uniformly at random. Enumerate ? = {? [?] ?/4:?(?) ???}. [?] ?/4:?(?) ?? ??}. Enumerate ? = {? Iterate over all ?,? ? ?s.t. a(L)+a(R)=t. Return YES if you encounter a disjoint pair. ? ? ?/4?= O(2.8113??) time. Takes ?/4+
The subsets L of S generate about 2?/2 sums Joux et al. 10 algorithm (a lot!). So we can guess a(L) modulo 2?/2 and reconstruct S via this subset! Assume ? = ?/2 for simplicity. Na ve algorithm: Joux et al. algorithm: Take ? 2?/2, ?? ? uniformly at random. Enumerate ? = {? [?] ?/4:?(?) ???}. [?] ?/4:?(?) ?? ??}. Enumerate ? = {? Iterate over all ?,? ? ?s.t. a(L)+a(R)=t. Return YES if you encounter a disjoint pair. ? ? ?/4?= O(2.8113??) time. Takes ?/4+
The subsets L of S generate about 2?/2 sums Joux et al. 10 algorithm (a lot!). So we can guess a(L) modulo 2?/2 and reconstruct S via this subset! Assume ? = ?/2 for simplicity. Na ve algorithm: Joux et al. algorithm: Take ? 2?/2, ?? ? uniformly at random. Enumerate ? = {? [?] ?/4:?(?) ???}. [?] ?/4:?(?) ?? ??}. Enumerate ? = {? Iterate over all ?,? ? ?s.t. a(L)+a(R)=t. Return YES if you encounter a disjoint pair. ? ? ?/4?= O(2.8113??) time. Takes ?/4+
The subsets L of S generate about 2?/2 sums Joux et al. 10 algorithm (a lot!). So we can guess a(L) modulo 2?/2 and reconstruct S via this subset! Assume ? = ?/2 for simplicity. Na ve algorithm: Joux et al. algorithm: Take ? 2?/2, ?? ? uniformly at random. Enumerate ? = {? [?] ?/4:?(?) ???}. [?] ?/4:?(?) ?? ??}. Enumerate ? = {? Iterate over all ?,? ? ?s.t. a(L)+a(R)=t. Return YES if you encounter a disjoint pair. ? ?/42 ?/2= 2.3113?. In expectation, ? , ? How enumerate ?,?? What is the failure probability? Since all elements of S are random, we expect small.
Enumerating L and R How to enumerate ? = {? Idea: use the same ideas before: Take ?2 dividing ?, guess ???. Enumerate ?? = {?? ? ?/4:?(?) ???}? [?] ?/8:?(??) ?2???}. [?] ?/8:?(??) ?2?? ???}. Enumerate ?? = {?? Iterate over all ?,? ?? ??s.t. a(LL)+a(LR)=??. List all pairs that are disjoint. ?? and ?? can be enumerated in (slightly) more na ve way.
Our technical contribution (variant) Let ? ? , |S|=n/2, p,q be primes ~2?/4 and ? ? ?/8} ? ? ? = { ?,??,?? :? ?/4,?? ?/8,?? ?,??,??,?? = ? ? % ??,? ?? %?,? ?? %? Then ?,?? ?3?/?3. Replaces the theorem on the `distribution of random knapsack sums by Nguyen et al. ( 01) used in the Joux et al. paper. Implies the promised ? 2.3399??4 time algorithm
Conclusions and Further Remarks ? 2.3399??4 time algorithm for Subset Sum Increases the set faster than HS solvable instances: from random ones to instances with ? 2.04?. Can be simplified a lot if we just aim at being faster than HS. Original ambition: Define ? = {? ? :? [?]}. Solve all instances with ? 2.9999? faster. Would imply that instances of density <1 are the hardest to solve faster than HS (by a hashing argument). Might be promising tool to improve HS in general. Recent research: we are close to answering YES?! Thanks!
