Tianrong Lin

Tianrong Lin

We prove in this paper that there is a language $L_s$ accepted by some nondeterministic Turing machine that runs within time $O(n^k)$ for any positive integer $k\in\mathbb{N}_1$ but not by any ${\rm co}\mathcal{NP}$ machines. Then we further show that $L_s$ is in $\mathcal{NP}$, thus proving a groundbreaking result that $$\mathcal{NP}\neq{\rm co}\mathcal{NP}. $$ The main techniques used in this paper are simulation and the novel new techniques developed in the author's recent work. Our main result has profound implications, such as $\mathcal{P}\neq\mathcal{NP}$, etc. Further, if there exists some oracle $A$ such that $\mathcal{P}^A\ne\mathcal{NP}^A={\rm co}\mathcal{NP}^A$, we then explore what mystery lies behind it and show that if $\mathcal{P}^A\ne\mathcal{NP}^A={\rm co}\mathcal{NP}^A$ and under some rational assumptions, then the set of all ${\rm co}\mathcal{NP}^A$ machines is not enumerable, thus showing that the simulation techniques are not applicable for the first half of the whole step to separate $\mathcal{NP}^A$ from ${\rm co}\mathcal{NP}^A$. Finally, a lower bounds result for Frege proof systems is presented (i.e., no Frege proof systems can be polynomially bounded).

Tianrong Lin

In this paper, we extend the techniques used in our previous work to show that there exists a probabilistic Turing machine running within time $O(n^k)$ for all $k\in\mathbb{N}_1$ accepting a language $L_d$ that is different from any language in $\mathcal{P}$, and then further to prove that $L_d\in\mathcal{BPP}$, thus separating the complexity class $\mathcal{BPP}$ from the class $\mathcal{P}$ (i.e., $\mathcal{P}\subsetneqq\mathcal{BPP}$). Since the complexity class $\mathcal{BQP}$ of {\em bounded error quantum polynomial-time} contains the complexity class $\mathcal{BPP}$ (i.e., $\mathcal{BPP}\subseteq\mathcal{BQP}$), we thus confirm the widespread-belief conjecture that quantum computers are {\em rigorously more powerful} than traditional computers (i.e., $\mathcal{P}\subsetneqq\mathcal{BQP}$). As an important consequence of the above results, we disprove the {\bf Extended Church--Turing Thesis}. Furthermore, we also show that (1): $\mathcal{P}\subsetneqq\mathcal{RP}$; (2): $\mathcal{P}\subsetneqq{\rm co-}\mathcal{RP}$; (3): $\mathcal{P}\subsetneqq\mathcal{ZPP}$. Previously, whether the above relations hold or not were long-standing open questions in complexity theory. Meanwhile, the result of $\mathcal{P}\subsetneqq\mathcal{BPP}$ shows that {\em randomness} plays an essential role in probabilistic algorithm design. In particular, we go further to show that (1): The number of random bits used by any probabilistic algorithm that accepts the language $L_d$ can not be reduced to $O(\log n)$; (2): There exists no efficient (complexity-theoretic) {\em pseudorandom generator} (PRG). $$ G:\{0,1\}^{O(\log n)}\rightarrow \{0,1\}^n; $$ (3): There exists no quick HSG $H:k(n)\rightarrow n$ such that $k(n)=O(\log n)$.

Deren Lin, Tianrong Lin

In this paper, we study the problem of model-checking quantum pushdown systems from a computational complexity point of view. We arrive at the following equally important, interesting new results: We first extend the notions of the {\it probabilistic pushdown systems} and {\it Markov chains} to their quantum counterparts, i.e., {\em quantum pushdown system (qPDS)} and {\em quantum Markov chains}, and prove a necessary and sufficient condition for a qPDS to be well formed, also presenting a method to extend the local transition function of a well-formed qPDS to a unitary local time evolution operator. Next, we investigate the question of whether it is necessary to define a quantum analogue of {\it probabilistic computational tree logic} to describe the probabilistic and branching-time properties of the {\it quantum Markov chain}. We study its model-checking question and show that model-checking of {\it stateless quantum pushdown systems (qBPA)} against {\it probabilistic computational tree logic (PCTL)} is generally undecidable, i.e., there exists no algorithm for model-checking {\it stateless quantum pushdown systems (qBPA)} against {\it probabilistic computational tree logic}. We then study in which case there exists an algorithm for model-checking {\it stateless quantum pushdown systems} and show that the problem of model-checking {\it stateless quantum pushdown systems (qBPA)} against {\it bounded probabilistic computational tree logic} (bPCTL) is decidable, and further show that this problem is in $\mathit{NP}$-hard. Our reduction is from the {\it bounded Post Correspondence Problem} for the first time, a well-known $\mathit{NP}$-complete problem.

Deren Lin, Tianrong Lin

In this paper, we define the notion of {\em probabilistic $ω$-pushdown automaton} and study its model-checking problem against the logic of $ω$-probabilistic computational tree logic ($ω$-PCTL) and its bounded version from a computational complexity view. Specifically, we obtain the following equally important new results: (1) We define {\em probabilistic $ω$-pushdown automaton} for the first time and study the model-checking question of {\em stateless probabilistic $ω$-pushdown system ($ω$-pBPA)} against $ω$-PCTL (defined by Chatterjee, Sen, and Henzinger in \cite{CSH08}), showing that model-checking of {\em stateless probabilistic $ω$-pushdown systems ($ω$-pBPA)} against $ω$-PCTL is generally undecidable. Our approach is to construct $ω$-PCTL formulas encoding the {\em Post Correspondence Problem}. (2) We then study in which case there exists an algorithm for model-checking {\it stateless probabilistic $ω$-pushdown systems} and show that the problem of model-checking {\it stateless probabilistic $ω$-pushdown systems} against $ω$-{\it bounded probabilistic computational tree logic} ($ω$-bPCTL) is decidable, and further show that this problem is $\mathit{NP}$-hard.