Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines

We prove in this paper that there exists 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 accepted by any ${\rm co}\mathcal{NP}$ machines. We further show that $L_s$ is in $\mathcal{NP}$, thereby prov