P vs NP (subset sum problem) - some thoughts

Discussions on everything related to the software, electronic, and mechanical components of information systems and instruments.

P vs NP (subset sum problem) - some thoughts

Postby DSblizzard on May 22nd, 2016, 8:09 am 

Problem statement
List of integers and integer are given. We need to find integers from list which sum to or answer that such integers don't exist - in polynomial time (from length of input). Original formulation is different, but we can easily convert it.

Strategy is to prove that or find where we stumble. I haven't proved anything serious, but I believe that my searchlight beams in right direction.

First, sort our list. We have . Then add to , to , to and so on. Now we have strict ordering: . Consider all possible orderings of sums of some elements in all possible lists of length . Here is example of ordering for :
For short I will write it in this way: _ 0 1 01 2 02 12 012 and denote SS (sum sequence).

Main idea
Find some ordering of all SS (there are about of them) and by binary search (or similar) find our SS. Then by another binary search in this SS find sum which is closest to given sum . Relevant paper:
Choose independent inequalities from SS. In our example they are: , , . Translate to geometric language: we have hyperplanes which bound chamber. In -dimensional space all SS are correspond to chambers and formed by intersection of hyperplanes. Each hyperplane have 2 normal vectors, which have coordinates lying in set . All of such vectors are used except . We will divide this full arrangement (FA) in subarrangements, which differ in number of zeros in their normal vectors. Each chamber in full arrangement uniquely characterized by chambers in subarrangements in which it is contained. I come to conclusion that for simplyfication of solution we should at first consider only "binary" arrangement (BA) - which doesn't contain zeros in normal vectors (it have relation to threshold logical functions, but "threshold arrangement" name is already used). This subarrangement have such advantage that it have much smaller number of vectors and chambers and conclusions to which we came as we study it usually can be generalized to full arrangement.

For BA consists of 14 chambers - 8 with 3 faces and 6 with 4 faces. If we cannot fully impose (make identical) 2 chambers by reflections and changes of coordinate axes, we say that they belong to different classes. There are (OEIS A109456):
  • 2 classes for ;
  • 3 for ;
  • 7 for ;
  • 21 for ;
  • 135 for .
Unfortunately count of classes also grows too fast: . Number of faces of dimension in dimension varies from to . But number of faces doesn't correspond to chamber "complexity". For example, to check, if point lies in chamber with maximal number of faces , which defined with these normal vectors:
    +++ ... ++
    +++ ... +-
    +-- ... --
we can easily: we should check that .

There is different property of chamber which mirrors its complexity: number of different classes of chambers which are adjacent to it. Experimentally i have found that this number grows as F+ (first as Fibonacci numbers, then faster). In ["On the Number of Facets of Polytopes Representing Comparative Probability Orders"] analogous fact is proven for full arrangement, but now I suspect that conjecture about growth of complexity of MCC (most complex chamber) as exact Fibonacci numbers is false. Couple of years ago I state these questions as most important:
  • How to describe chambers in n dimensions if we have descriptions for smaller dimensions (how to describe them recursively)?
  • Can we polynomially describe positions in SS where is present (for given )?
  • Which operations in algorithm we should consider, can we use only summation and comparison operations?
Each chamber in FA and BA have invariant - sum of vectors which "looks" in direction of chamber. For example, for point in BA we should sum vectors
    + - +
    + - -
    - - +
    - - -
and invariant is . Invariant for points lying in simple chambers we can find easily, but for MCC i failed to obtain invariant in polynomial time.

BUT... MCC in some way is very simple chamber: point always lies in it and we can use Ramanujan-Hardy-Rademacher formula for finding invariant in polynomial time. If we somehow managed to find last digits of in polynomial time even if is exponential (say, ), this would be a strong hint that and are equal ant hint as to where we should go next. We should not try to tie all vectors of chamber in polynomial bunch, but consider all numbers in invariant independently - this is main conclusion to which i came. And different exponential barriers ( or ) to which I inevitably hit, when trying to collect all vectors together can be used to prove that we cannot prove that in some certain way. But I won't prove it myself.

BTW, there are 2 sets of chamber vectors which we should consider - first is faces of chamber and second is all vectors which "look" at chamber. First set is smaller, but second is conceptually simpler.

Re: P vs NP (subset sum problem) - some thoughts

Postby Natural ChemE on June 19th, 2016, 3:31 am 


Welcome to the forums!

I moved your thread from Mathematics to Computers, since is traditionally considered a Computer Science problem, in the subfield of classifying algorithms by time complexity.

The subset sum problem seems like a good way to approach the problem since it's a pretty straightforward -problem to try to do in -time.

I'm going to edit your OP a tad to make it more legible, then probably post more on here later. It's a fun problem to play with!
Natural ChemE
Forum Moderator
Posts: 2746
Joined: 28 Dec 2009

Re: P vs NP (subset sum problem) - some thoughts

Postby Natural ChemE on June 20th, 2016, 5:54 am 


After skimming the post, my impression's that you're basically providing a geometric interpretation of an -time problem, then attempting to move toward a solution in -time.

It's standard practice for people trying to solve a problem like this to first interpret it into their analytical domain of choice, yours apparently being geometry. Had the problem statement been in French, you'd have first translated it to English too.

So while the interpretation is neat, I'm not picking up on any advancement toward solving the underlying problem. If you were to try to publish work like this, I'd characterize the paper as providing a geometric interpretation of the sum subset problem.

I'd note that reinterpretations can be neat. For example, a few years back someone reinterpreted the problem into the analytical domain of Minesweeper, which made headline news in academia:It's been a while since I've read that paper, so take this with a grain of salt, but I think that your problem can be mapped to Minesweeper like this:
  1. Start with your geometric interpretation of the sum subset problem.
  2. Map it back to the original sum subset problem.
  3. Through the collective net of -time mappings, map the sum subset problem to whatever -time problem the Minesweeper guy worked off of, which I think was something about circuit diagrams.
  4. Follow the Minesweeper guy's mapping to Minesweeper.
Finally, as a general note, I think that is more of an ontological question; that merely attempting to provide a -time algorithm, while of extreme interest, is short-selling the actual question. I'd think that it'd be more fruitful to address why we can't map the collection of -time problems to -time, which would require a consideration of the underlying rule set (physics, axioms, or whatever your field calls them). Ideally would be proven by someone's failed attempt to disprove it, rather than vice-versa.
Natural ChemE
Forum Moderator
Posts: 2746
Joined: 28 Dec 2009

Return to Computers

Who is online

Users browsing this forum: No registered users and 3 guests