6 citations · 8 across the 10 of their papers we have counts for
10 papers
Probabilistic Computers (and Hence Quantum Computers) Are Rigorously More Powerful Than Classical Deterministic Computers, and Derandomization
Tianrong Lin
In this paper, we extend the techniques developed in our previous work to construct a probabilistic Turing machine that runs within time for every and a…
On Probabilistic -Pushdown Systems, and -Probabilistic Computational Tree Logic
Deren Lin, Tianrong Lin
In this paper, we define the notion of a {\em probabilistic -pushdown automaton} and study its model-checking problem against -probabilistic computational tree logic (-PCT…
On Baker-Gill-Solovay Oracle Turing Machines and Relativization Barrier
Tianrong Lin
This work analyses the so-called "Relativization Barrier" with respect to the Baker-Gill-Solovay oracle Turing machine. We show that the {\em diagonalization} technique is a valid…
Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
Tianrong Lin
The {\em diagonalization technique} was invented by Georg Cantor to show that there are more real numbers than algebraic numbers and is very crucial in {\em theoretical computer sc…
Resolution of The Linear-Bounded Automata Question
Tianrong Lin
This paper resolves a famous and longstanding open question in automata theory, i.e., the {\it linear-bounded automata question} (or, for short, the LBA question), which can also b…
The Separation of and
Tianrong Lin
There is an important and interesting open question in computational complexity on the relation between the complexity classes and . It is a widesp…