Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines

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 $\mathrm{c}\mathrm{o}\mathcal{N}\mathcal{P}$ machines. Then we further show that $L_s$ is in $\mathcal{N}\mathcal{P}$, thus proving a groundbreaking result that $$\mathcal{N}\mathcal{P}\mathrm{\ne }\mathrm{c}\mathrm{o}\mathcal{N}\mathcal{P}\mathrm{.}$$ 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}\mathrm{\ne }\mathcal{N}\mathcal{P}$, etc. Further, if there exists some oracle $A$ such that ${\mathcal{P}}^A\mathrm{\ne }{\mathcal{N}\mathcal{P}}^A=\mathrm{c}\mathrm{o}{\mathcal{N}\mathcal{P}}^A$, we then explore what mystery lies behind it and show that if ${\mathcal{P}}^A\mathrm{\ne }{\mathcal{N}\mathcal{P}}^A=\mathrm{c}\mathrm{o}{\mathcal{N}\mathcal{P}}^A$ and under some rational assumptions, then the set of all $\mathrm{c}\mathrm{o}{\mathcal{N}\mathcal{P}}^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{N}\mathcal{P}}^A$ from $\mathrm{c}\mathrm{o}{\mathcal{N}\mathcal{P}}^A$. Finally, a lower bounds result for Frege proof systems is presented (i.e., no Frege proof systems can be polynomially bounded).