0
$\begingroup$

Where is there a gap or error in my reasoning?

The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1).

The compression algorithm in brief:

  1. check if the size of the set r +1 is a power of two. If not, terminate compression
  2. check all combinations without repetition of size log2(r+1) if any of them can be decompressed (summing all possible subsets without empty subset) to the set r of numbers. If so, return the combination
  3. if no suitable combination is found, terminate compression.

The subset sum problem is to check whether the set r of numbers (that is, the set of sums of subsets of the set n of numbers) contains the number you are looking for. To do this, you can represent the set r of numbers as an array and search it. Searching the array in the worst case requires checking each element, which is O(r) (for a decompressed set) or O(2^n) (for a compressed set). Faster ways such as binary search are known, but they require knowledge of the ordering of numbers, so that by checking one number we also gain knowledge of where to look for other numbers. Without knowing anything about the ordering of the numbers in the array, you can't search the array faster than linearly, because by checking the numbers one by one, you don't get any knowledge of where the number you're looking for might be.

Does the compressed set of n numbers have information about the ordering of the array of r numbers? No.

The number of possible orderings of a set r of numbers is r!, or ((2^n)-1)!, which is a number greater than n! Pigeonhole principle says that if we have 'a' objects that we put into b drawers and a > b then there must be at least one drawer where there will be at least two objects. According to this rule, the set of n numbers cannot contain explicit information about the ordering of the elements in the array r of numbers, because many orderings of the array r of numbers can be compressed into the same array of n numbers, with the same elements and their ordering, and we do not get any other information besides this set. The ways to generate combinations in the compression algorithm are many, by which we can consider that every ordering of an array r of numbers can be compressed into every possible ordering of a set of n numbers.

If the subset sum problem is in P, then there exists a search algorithm that will answer the subset sum problem in polynomial time calculated from the size of the compressed set of n numbers. From this, we can conclude that to find a number in an array r of numbers in faster than linear time, it is sufficient to subject the array to lossy compression rather than sorting. When we subject the sorted array r of numbers to compression, we retain the ability to search it in faster-than-linear time, despite the fact that the compression was lossy and as a result, we lost ordering knowledge and most of the content knowledge. The data can be reconstructed, but only by generating the sums of every possible subset and sorting them, since we know from principle pigeonhole that the original ordering knowledge has been lost and must be acquired anew.

Losing knowledge of the ordering of an array r of numbers ( and most of its contents) while still being able to search it in faster than linear time does not make sense, from which it follows that there is no algorithm that allows this, which means that the subset sum problem is not in P, and since SSP is in NP then P != NP.

$\endgroup$
4
  • $\begingroup$ I didn't fully read your post, but I highly doubt you can prove that easily that $P\neq NP$. Its a hard question that a lot of people constantly thought about for a long time already, and no one has reached a conclusion yet (or is close to reach a conclusion!). $\endgroup$
    – nir shahar
    May 9 at 12:34
  • $\begingroup$ @nirshahar I suspect so too, but I'm curious to know where the error is in this case. $\endgroup$
    – Pajzano
    May 9 at 12:54
  • 1
    $\begingroup$ This statement is wrong: From this, we can conclude that to find a number in an array r of numbers in faster than linear time, it is sufficient to subject the array to lossy compression rather than sorting. $\endgroup$ May 9 at 19:01
  • $\begingroup$ The structure of subset sum can be used to give an $O^*(2^{n/2})$ algorithm, using meet-in-the-middle: generate all sums of the first n/2 integers and sort them, then go over all sums of the other n/2 integers and use binary search on the first array to look for a solution. $\endgroup$ May 9 at 19:11
1
$\begingroup$

The subset sum problem is quite different from your problem: Given a list of integers and a target sum $S$, it asks if there is a subset of the list that sums to $S$. No "compression", lossy or not. Any lossy technique will (by definition) tend to miss the target (because it works with an approximation). And we are looking for an exact solution, not one that is 10% off, it has to be right on.

It looks to me that the collection of subsets for which you need to compute the sums is even larger than the numbers in the original list. If so, it isn't any speedup.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.