# Are all languages in P?

Are all languages in $\mathbf{P}$?

Note: The definitions of all the symbols and functions here follow the document [1].

The following is my attempt to answer the question. Assume that we design a special Turing machine $M_1$, no matter what the input is, $M_1$ will jump to the state $q_{\rm accept}$ (the accepting state). Because no matter what the input $w$ is, $M_1$ only needs one step to finish the calculation, $T_{M_1}(n) = 1\ \forall n \in \mathbb{N}$. Let $k=1$, then $T_{M_1}(n) \leq n^1 + 1 = n + 1$. Therefore, $M_1$ runs in polynomial time. Then, all languages $L$ are in $\mathbf{P}$.

## Reference

[1] S. Cook, The P versus NP problem, [Online] http://www.claymath.org/sites/default/files/pvsnp.pdf.

• You already have a good answer, so I will only add that you have shown that the language $\Sigma^{*}$ is in P (in fact, it runs in constant time), so all strings are acceptable in constant time, but not all languages. Similarly, the language $\emptyset$ is decideable in constant time, by a machine that jumps immediately to $q_{\text{reject}}$. – Lieuwe Vinkhuijzen May 16 '16 at 9:30

You are misunderstanding how accepting a language works. A language $L$ is in P iff there is a deterministic Turing Machine that decides whether a word $w$ belongs to $L$ in polynomial time. Deciding means that it return a positive answer iff $w \in L$ and a negative otherwise.
Your approach will return a positive answer in every case. Thus your TM will accept the language $\Sigma^*$ where $\Sigma$ is the input alphabet of your TM.
• No, a language $L$ is in NP, iff there is a non-deterministic turing machine that decides whether a word $w$ belongs to $L$ in polynomial time. – Martin Glauer May 17 '16 at 4:05
• @MillieSmith Note that when speaking of turing machines the terms "decides" and "recognizes" have precise meanings. The term "decide" already implies that for every word $w$ the Turing machine halts with a yes or no answer, while "recognizes" means that if $w \in L$ then the machine halts with yes, but if $w \notin L$ then the machine may not halt. However this isn't about complexity classes but about decidability of the languages. – Bakuriu May 17 '16 at 7:16