Portal de Periódicos da CAPES

Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy

1993; Elsevier BV; Volume: 113; Issue: 1 Linguagem: Inglês

10.1016/0304-3975(93)90214-e

1879-2294

Jun Tarui,

Advanced Graph Theory Research

We show that, for every Boolean function f(x1, …, xn) in the class AC0 and an arbitrary constant k⩾0, there is a size-O(nk + 1) collection Ω of degree-logO(1)n polynomials over Z in x1, …, xn such that, for each x∈{0, 1}n, when p ∈ Ω is randomly chosen, f(x) = p(x) with probability at least 1 − 1/(3nk), and, furthermore, if f(x) = 0 (f(x) = 1), then p(x) = 1 (p(x) = 0) with probability 0. Applying this result, we prove the following: (a) Every Boolean function in the class AC0 can be computed with one-sided error at most 1/(3nk) by some depth-two probabilistic circuits with a threshold gate at the root, nlogO(1)n AND gates of fan-in logO(1)n at the next level, and (k + 1)log2n + O(1) random bits; it can also be computed, for an arbitrary constant l ⩾ 0, by some depth-three deterministic circuits with an OR gate at the root, at most n/(log2n)l Threshold gates at the second level, and nlogO(1)n AND gates of fan-in logO(1)n at the third level. (b) For C = PP, C = P, and MODmP, every language L in the polynomial-time hierarchy is C-easy under a randomized many-one polynomial-time reduction; in fact, for C = PP and C = P, L is C-easy under such a reduction with one-sided error.