1
$\begingroup$

In the wikipedia page for Toda's Theorem, the notation $A\cdot B$ is used where $A$ and $B$ are two complexity classes, but without explanation as to its meaning.

SO given two classes $A$ and $B$ what does $\cdot$ mean in $A\cdot B$?

Using an example for the cited page, what would $BP \cdot \oplus P$ mean?

Is it correct to say $A\cdot A=A$, and when is it true that $A\cdot B=B$ or $A$?

$\endgroup$
3
$\begingroup$

Reading Toda's original paper, it's not clear that a general application of $\cdot$ has meaning, however it may have been extended later.

Toda introduces three operators: $\oplus\cdot$, $\mathsf{BP}\cdot$ and $\mathsf{C}\cdot$, so the $\cdot$ is, in this context, not an independent piece of notation. Toda is extending the $\mathsf{BP}\cdot$ operator introduced by Schöning (but with uglier notation - $BP\mathscr{C}$ for the operator applied to class $\mathscr{C}$).

The three operators give (intuitively) the closures of classes under three different types of reductions. I'll reproduce the definition (and intuitive explanation) for $\mathsf{BP}\cdot$ for Toda's paper (p. 867):

$L \in \mathsf{BP}\cdot\mathbf{K}$ if there exist a set $A \in \mathbf{K}$, a polynomial $p$, and a constant $\alpha > 0$ such that, for all $x\in \Sigma^{\ast}$, $$ \text{Prob}(\{w\in\{0,1\}^{p(|x|)}:x\#w\in A \leftrightarrow x \in L\}) \geqq \frac{1}{2}\alpha $$

The intuitive definition is (p. 865):

Intuitively speaking, a set is in $\mathrm{BP}\cdot\oplus \mathbf{P}$ if and only if it is reducible to a set in $\oplus\mathbf{P}$ under a polynomial-time randomized reduction with two-sided bounded error probability.

$\endgroup$
1
$\begingroup$

There is no such notation. The piece of notation you are citing is $\mathsf{BP} \cdot \mathsf{X}$, which is the bounded probabilistic version of $\mathsf{X}$, that is, $\mathsf{BP}\cdot\mathsf{X}$ has the same relation to $\mathsf{X}$ as $\mathsf{BPP}$ has to $\mathsf{P}$.

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