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$
2
$\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}$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.