6 citations · 8 across the 10 of their papers we have counts for
4 papers · 2 filters
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…