1
$\begingroup$

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}}) $ enter image description here 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?

$\endgroup$
1
$\begingroup$

Suppose all $x_i$ are equal to one and $n$ is even (so there is a solution). Suppose that in every step, a smallest remaining $I \in S$ is 'randomly' chosen. It is then discarded along with all of its subsets - which are not in $S$ anymore anyways by minimality of $I$.

You thus keep discarding single sets until you have eliminated all of size $< n/2$, of which there are $\sum_{j=1}^{n/2-1} \binom{n}{j} \sim 2^{n-1}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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