Complexity Classes Characterized by Semi-Random Sources
Ryuhei Uehara · Institutional Repositories DataBase (IRDB) · 1996
: The complexity classes PP; BPP and RP are usually defined via probabilistic Turing machines (PTMs) that have access to a perfect random source. A natural question is this: Do these classes change if the PTMs only have access to an arbitrary semi-random source rather than a perfect random source? The notion of semi-randomness are defined by Satha and Vazirani in 1984, and this question was first considered by Vazirani and Vazirani in 1985, who proved that RP does not change even if the PTMs only have access to an arbitrary semi-random source. Later, Vazirani proved that BPP does not change, either. In this paper, we show a surprising result that PP collapses to BPP if the PTMs only have access to an arbitrary semi-random source. We also consider the following question: Do the classes PP; BPP and RP change if the PTMs only have access to a specific semi-random source? As answers to this question, we show that RP changes to NP while both BPP and PP change to PSPACE. P = 8 0-RP = ...