5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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}}$. $\endgroup$ – Lieuwe Vinkhuijzen May 16 '16 at 9:30
20
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "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." Wouldn't that mean L is in NP but not necessarily P? $\endgroup$ – Millie Smith May 17 '16 at 0:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Glauer May 17 '16 at 4:05
  • 1
    $\begingroup$ @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. $\endgroup$ – Bakuriu May 17 '16 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.