We consider a class, denoted APP, of real-valued functions f : f0; 1g n ! [0; 1] such that f can be approximated, to within any ffl ? 0, by a probabilistic Turing machine running in time poly(n; 1=ffl). We argue that APP can be viewed as a generalization of BPP, and show that APP contains a natural complete problem: computing the acceptance probability of a given Boolean circuit; in contrast, no complete problems are known for BPP. We observe that all known complexity-theoretic assumptions under which BPP is easy (i.e., can be efficiently derandomized) imply that APP is easy; on the other hand, we show that BPP may be easy while APP is not, by constructing an appropriate oracle. 1 Introduction The complexity class BPP is traditionally considered a class of languages that can be efficiently decided with the help of randomness. While it does contain some natural problems, the "semantic" nature of its definition (on every input, a BPP machine must have either at least 3=4 or at...
We consider a class, denoted APP, of real-valued functions f : f0; 1g n ! [0; 1] such that f can be approximated, to within any ffl ? 0, by a probabilistic Turing machine running in time poly(n; 1=ffl). We argue that APP can be viewed as a generalization of BPP, and show that APP contains a natural complete problem: computing the acceptance probability of a given Boolean circuit; in contrast, no complete problems are known for BPP. We observe that all known complexity-theoretic assumptions under which BPP is easy (i.e., can be efficiently derandomized) imply that APP is easy; on the other hand, we show that BPP may be easy while APP is not, by constructing an appropriate oracle. 1 Introduction The complexity class BPP is traditionally considered a class of languages that can be efficiently decided with the help of randomness. While it does contain some natural problems, the "semantic" nature of its definition (on every input, a BPP machine must have either at least 3=4 or at...
We show that for deterministic polynomial time computations, oracle access to
APP, the class of real functions
approximable by probabilistic Turing machines, is the same as having oracle access to
promise-BPP. First,
we construct a mapping that maps every function in APP to a promise problem
in prBPP, and that preserves completeness, i.e. maps complete functions to complete promise problems.
Next, we construct
a mapping from
prBPP into APP, that maps every promise problem to a function
in APP, and which preserves completeness.
Then, we prove that PAPP=PprBPP.
Finally, we use our results to simplify proofs of important results on APP, such as
the APP-completeness of the function fCAPP,
which approximates the acceptance
probability of a Boolean circuit, the error probability reduction Theorem
for APP functions, and the conditional derandomization result
APP=AP iff prBPP is easy.
In this paper, we extend the techniques developed in our previous work to construct a probabilistic Turing machine that runs within time O(nk) for every k∈N1 and accepts a language Ld∈/P. We further show that Ld∈BPP, thereby separating BPP from P (i.e., P⫋BPP). Since the complexity class BQP of {\em bounded error quantum polynomial-time computation} contains BPP (i.e., BPP⊆BQP), our result confirms the long-standing conjecture that quantum computers are {\em rigorously more powerful} than classical deterministic computers (i.e., P⫋BQP). As an important consequence of the above results, we disprove the {\bf Extended Church-Turing Thesis}. Furthermore, we establish the following separations: (1) P⫋RP; (2) P⫋coRP; (3) P⫋ZPP. These relationships were long-standing open questions in complexity theory. In addition, the separation P⫋BPP demonstrates that {\em randomness} plays an essential role in probabilistic computation. In particular, we prove the following: (4) The number of random bits used by any probabilistic algorithm accepting Ld cannot be reduced to O(logn); (5) There exists no efficient (complexity-theoretic) {\em pseudorandom generator} (PRG): G:{0,1}O(logn)→{0,1}n; (6) There exists no quick HSG H:k(n)→n with k(n)=O(logn).
This paper proves that every language in NP is recognized by an RP[ \\Phi P] machine whose time complexity is quasilinear, apart from the time to verify witnesses. The results significantly improve the number of random bits, success probability, and running time of Valiant and Vazirani's original construction [VV86], and beat both the 2n random bits and time/success tradeoff in subsequent methods based on universal hashing. Questions of further improvements are connected to open problems in the theory of error-correcting codes. 1. Introduction Valiant and Vazirani [VV86] proved that every language L 2 NP is accepted by a polynomial-time bounded probabilistic oracle Turing machine M o which, on any input x, computes a Boolean formula OE x as an oracle query, and accepts if the answer is `1'. The oracle of M o has the "promise property" that whenever OE x has a unique satisfying assignment, it always answers `1', and whenever OE x has no satisfying assignments, it answers `0'. An ...
Polylogarithmic time delineates a relevant notion of feasibility on several classical computational models such as Boolean circuits or parallel random access machines. As far as the quantum paradigm is concerned, this notion yields the complexity class FBQPOLYLOG of functions approximable in polylogarithmic time with a quantum random-access Turing machine. We introduce a quantum programming language with first-order recursive procedures, which provides the first programming-language-based characterization of FBQPOLYLOG. Each program computes a function in FBQPOLYLOG (soundness) and, conversely, each function of this complexity class is computed by a program (completeness). We also provide a compilation strategy from programs to uniform families of quantum circuits of polylogarithmic depth and polynomial size, whose set of computed functions is known as QNC, and recover the well-known separation result FBQPOLYLOG ⊊ QNC.
We consider the class of counting problems,i.e. functions in #P, which are self reducible, and have easy decision version, i.e. for every input it is easy to decide if the value of the function f(x) is zero. For example, #independent-sets of all sizes, is such a problem, and one of the hardest of this class, since it is equivalent to #SAT under multiplicative approximation preserving reductions. Using these two powerful properties, self reducibility and easy decision, we prove that all problems/ functions f in this class can be approximated in probabilistic polynomial time within an absolute exponential error ε⋅2n′,∀ε>0, which for many of those problems (when n′=n+constant) implies additive approximation to the fraction f(x)/2n. (Where n′ is the amount of non-determinism of some associated NPTM). Moreover we show that for all these problems we can have multiplicative error to the value f(x), of any desired accuracy (i.e. a RAS), in time of order 22n′/3poly(n), which is strictly smaller than exhaustive search. We also show that $f(x)
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn) NP queries, then BPPNP[o(n)] contains a PNP-complete problem if the algorithm is classical and FBQPNP[o(n)] contains an FPNP-complete problem if the algorithm is quantum.