HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Are all languages in P?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
arelanguagesall

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#57518, answer score: 20

Revisions (0)

No revisions yet.