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:
- check if the size of the set r +1 is a power of two. If not, terminate compression
- 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
- 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.
