1
$\begingroup$

Let's define $PP_c$ as a set of languages: A language $L$ is in $PP_c$ iff there exists a polynomial $p: \mathbb{N} \rightarrow \mathbb{N}$ and a polynomial time turing machine $P$ s.t. if $x \in L$ then $Pr[P(x, u) = 1] \geq c$ and if $x \notin L$ then $Pr[P(x, u) = 1] < c$, where $u \in \{0,1\}^{p(|x|)}$. I have learned that $PP = PP_{0.75}$, other sources define $PP = PP_{0.5}$.

Does $PP = PP_c$ hold for every $0 < c < 1$? Or what are adequate restrictions for $c$ s.t. $PP = PP_c$?

1 Answers 1

3

You're right that $PP=PP_c$ for every $0 < c < 1$.

Given an algorithm in $PP_c$ for $c > 1/2$, define a new algorithm that outputs $0$ with probability $1-1/2c$, and runs the original algorithm otherwise (with probability $1/2c$). Now the threshold is moved from $c$ to $1/2c \cdot c = 1/2$.

You can work yourself how to transform a $PP_c$ algorithm with $c < 1/2$ to $PP_{1/2}$, and how to transform $PP_{1/2}$ to $PP_c$ for $c \neq 1/2$ (consider two cases).

  • 0
    On second thought, the general argument has just two cases: c < d and c > d (for showing $PP_c = PP_d$).2011-05-31