2
$\begingroup$

Let $S_1$ and $S_2$ are two multi sets. We want to find, Is $S_1 =S_2$?

Algo 1:

Sort $S_1$ and $S_2$ and then check $S_1 = S_2$

Running time : $O(n \log {n})$, where $n$ is the size of the multi sets.

Algo 2:

Contruct two polynomials using $S_1$ and $S_2$ (example if $S_1 = \{1,1,2\}$ then polynomial will be $(x-1)(x-1)(x-2)$)

Let us say we have now two polynomials $p(x)$ and $q(x)$, do $p(x)-q(x)$, now using polynomial identity testing check whether $p(x)-q(x) =0 $ or not. If it is zero then $S_1$ equals to $S_2$.

Question : Which algorithm is better Algo 1 or Algo 2?

$\endgroup$
  • 4
    $\begingroup$ How about defining better? Time wise? $\endgroup$ – Eugene Nov 15 '17 at 6:04
  • 1
    $\begingroup$ How about Algo3: Iterating throug $S_1$ and removing from $S_2$. If an element doesn't exists in $S_2$ or $S_2$ is not empty at the end, then $S_1 \neq{} S_2$. The running time is $O(n)$, if element test and element remove are in $O(1)$. $\endgroup$ – clemens Nov 15 '17 at 6:56
  • 2
    $\begingroup$ Where is there randomness here? $\endgroup$ – Raphael Nov 15 '17 at 7:28
  • 1
    $\begingroup$ @Raphael: Suppose the set implementation is based on hashing, and duplicates are just implemented by counters. This fulfils my restriction to $O(1)$ for testing and removing. Than Algo3 should use $O(n)$, or is there something I don't understand? $\endgroup$ – clemens Nov 15 '17 at 7:37
  • 3
    $\begingroup$ @Raphael Polynomial identity testing is randomized: you substitute a random element and see whether both sides agree. $\endgroup$ – Yuval Filmus Nov 15 '17 at 7:40
1
$\begingroup$

To understand the complexity of the randomized algorithm, you must delve into the implementation details.

Suppose $S_1,S_2$ consist of $m$ elements, each bounded by $n$ in absolute value, i.e. the input size is $O(m\log n)$. Let $P_S=\prod\limits_{w\in s}\left(x-w\right)$ be the polynomial corresponding to the set $S$. $P_{s_1},P_{S_2}$ are degree $m$ polynomials. Thus, in order to succeed with constant probability in testing whether $q(x)=P_{S_1}(x)-P_{S_2}(x)$ is the zero polynomial, you need to evaluate it at numbers in the range $[0,cm]$, for some constant $c$.

Suppose you choose $y$ uniformly at random from this range, then in order to avoid blowup in the intermediate values while computing $q(y)$, you need to compute the values modulo some $k$ (the standard trick in PIT).

Note that the blowup here is not exponential, unlike in PIT where the polynomials are given as algebraic circuits, so you can in fact directly compute $q(y)$. However, this will lead to handling $\Omega(m)$ bit numbers, which will result in quadratic running time, so you can still compute $q(y) \bmod k$ for a random $k$ chosen appropriately to save some time.

If $k$ is chosen at random from some range $[1,R]$, then a "good" event is that $k$ does not divide $q(y)$, in that case $q(y)\neq 0$ iff $q(y) \bmod k \neq 0$. To lower bound this probability, note that $k$ is prime with probability $\approx \frac{1}{\log R}$ (here you need some finite version of the prime number theorem), and that $q(y)\le (cm+n)^m$, hence it has at most $m \log (cm+n)$ different prime factors.

$ \begin{align*} & \Pr\limits\left[\text{$k$ is prime $\land$ $k$ is not a product of $q(y)$}\right]= \Pr\left[\text{$k$ is prime}\right]\cdot\\ & \Pr\limits\big[\text{$k$ is a product of $q(y)$} \big| \text{$k$ is prime}\big]\approx \frac{1}{\log R}\left(1-\frac{\log (cm+n)^m}{R/\log R}\right) \end{align*} $

Choosing $R=(m+n)^2$ suffices to make the above probability high enough, and yields constant success probability after $\approx\log R$ evaluations. Each evaluation requires $O(m)$ additions/multiplications of numbers with $\log R$ bits, thus the overall running time is $O(m\log ^2 R\log\log R)$, which is worse than sorting. Perhaps sharper bounds on the success probability will allow you to get rid of one of the logarithmic factors, but taking numeric operations into account will eventually show that you cant beat naive sorting. However, the randomized approach is not without merits, as it allows you to determine multiset equality between two parties with logarithmic communication (you only need to send $y,k$ and the evaluations of $P_{S_1},P_{S_2}$ on $y$ modulo $k$).

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