2023/08/18 by Tianrong Lin, Lin, Tianrong
Computer Science · Mathematics · #Algorithm #Bounded function #Class (philosophy) #Combinatorics #Complexity and Algorithms in Graphs #Complexity class #Computability, Logic, AI Algorithms #Computer science #Conjecture #DTIME #Discrete mathematics #Mathematics #Physics #Probabilistic logic #Pseudorandom number generator #Quantum #Quantum Computing Algorithms and Architecture #Quantum complexity theory #Quantum computer #Quantum mechanics #Randomness #Time complexity #Turing machine #Universal Turing machine
paper · pdf · doi:10.48550/arxiv.2308.09549
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2023/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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∈ℕ1 and accepts a language Ld\notinP. We further show that Ld\inBPP, thereby separating BPP from P (i.e., P\subsetneqqBPP). Since the complexity class BQP of \em bounded error quantum polynomial-time computation contains BPP (i.e., BPP\subseteqBQP), our result confirms the long-standing conjecture that quantum computers are \em rigorously more powerful than classical deterministic computers (i.e., P\subsetneqqBQP). As an important consequence of the above results, we disprove the \bf Extended Church-Turing Thesis. Furthermore, we establish the following separations: (1) P\subsetneqqRP; (2) P\subsetneqq\rm coRP; (3) P\subsetneqqZPP. These relationships were long-standing open questions in complexity theory. In addition, the separation P\subsetneqqBPP 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(log n); (5) There exists no efficient (complexity-theoretic) \em pseudorandom generator (PRG): G:\0,1\O(log n)→ \0,1\n; (6) There exists no quick HSG H:k(n)→ n with k(n)=O(log n).