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 :

- .

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:

- The Enumeration of Comparative Probability Relations, Terrence Fine and John Gill (1976).

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 .

- +++ ... ++

+++ ... +-

...

+-- ... --

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?

- + - +

+ - -

- - +

- - -

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.