EDIT: I realized that if $J$ is not a solution so is $J^c$. I updated the algorithm because of this.
Given some positive integers $x_1,\cdots, x_n$.
The following algorithm is for solving the partition problem: $\sum_{i \in I} x_i = \sum_{j\in I^C} x_j$
The "idea" behind it is, to remove unnecessary subsets from the search space:
If $\sum_{i \in I} x_i < \sum_{j\in I^C} x_j$ then we will remove the powerset $P(I)$ from the search space $S$, because then each subset $J\subseteq I$ is not a solution. We will also remove $J^c$ from $S$ for each $J \subseteq I$, because those also cannot be solutions.
Simlilarly if:
If $\sum_{i \in I} x_i > \sum_{j\in I^C} x_j$ then we will remove the powerset $P(I^c)$ from the search space $S$, because then each subset $J\subseteq I^c$ is not a solution. We will also remove $J^c$ from $S$ for each $J \subseteq I^c$, because those subsets cannot be solutions.
I have investigated the situation empirically with input $x_1=\cdots=x_n=1$, $n = $ odd, and have come to an approximate formula for $|S|$ after each step, but I don't know how to prove it. Any help would be appreciated:
1) Set S := P([n]), the powerset of {1,..,n}
2) while |S| > 0:
3) randomly choose some I from S
4) S := S - {I,I^c}
5) if sum_{I} x_i < sum_{I^c} x_j:
6) S := S - P(I) # remove all subsets of I from the search space
7) for each J in P(I): # remove all corresponding complements from the search space
8) S := S - {J^c}
9) if sum_{I} x_i > sum_{I^c} x_j:
10) S := S - P(I^c) # remove all subsets of I^c from the search space
11) for each J in P(I^c): # remove all corresponding complements from the search space
12) S := S - {J^c}
13) if sum_{I} x_i = sum_{I^c} x_j:
14) print "solution found", exit
15) print "no solution exists"
The "time" should be measured as how many subsets $I \in S$ are chosen:
Each loop in the while loop counts as one step.
I have implemented this algorithm in python to get a feeling for it.
With input $x_i = 1$, $n = $ odd (so there does not exist a solution) then it seems like we have:
$f(x) \equiv 2^n -a_1 \log(x) - a_2 \log(x)^2$ for some $a_1,a_2$
where $f(x)$ is the number of elements in $S$ after $x$ steps.
The function on the right hand side above satisfies the following differential equation:
$f'(x) = \frac{\sqrt{c(2^n-f(x))+b}}{x}$, maybe this is of some help.
If it was true, that $f(x) \equiv 2^n-a_1 \log(x) - a_2\log(x)^2$ then the number of queries $I \in S$ would be approximately:
$x \equiv \exp(\frac{-a_1}{2a_2}+\sqrt{\frac{a_1^2}{4a_2^2}+\frac{2^n}{a_2}})
$ 
The blue line represents the fitted line.
Does somebody have an explanation for this?
How do the constants $a_1,a_2$ depend on $n$?
EDIT: I made some further empirical investigations: Let $Y:=x(f(x)-f(x+1))$ be the random variable defined through the algorithm on input $x_1=\cdots=x_n=1$, $n=$odd, $1 \le x \le l$, where $l=$number of queries $ I \in S$. Then I am interested in the standard-deviation $\sigma_Y$ of $Y$.
Q1) Is it true that we have: $\sigma_Y = \frac{2^n}{\log(l)\cdot(1+\epsilon)}$ for some small $\epsilon>0$.
Q2) Is it true that for for all $1 \le x \le l$ we have $f(x) \ge 2^n (1-\frac{\log(x)}{\log(l)})$
To each search space $S_m$ in the while loop, we might measure its entropy: $ H_m = - \sum_{I \in S_m} \frac{1}{|S_m|} \cdot -\log(|S_m|) = \log(|S_m|)$ Hence the information gain from step $m$ to step $m+1$ is $ H_m-H_{m+1} = \log(|S_m|)-\log(|S_{m+1}|)$.
Q3) Is there any way which I might have missed such that the information gain becames greater then the current value in each step? In other words: Can we remove more subsets after each experiment in the while loop? Or can we prove that the information gain is maximal in each step already?
