Return to Answer

$\mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXPTIME}$ etc. are all complexity classes. This means they contain problems, not algorithms. An algorithm can never be in $\mathsf{P}$, but if there's a polynomial-time algorithm solving a given problem $X$, then $X$ is in $\mathsf{P}$. There could also be a bunch of exponential-time algorithms accepting $X$, but since there exists a single polynomial-time algorithm accepting $X$, it is in $\mathsf{P}$.

$\mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXPTIME}$ etc. are all complexity classes. This means they contain problems, not algorithms. An algorithm can never be in $\mathsf{P}$, but if there's a polynomial-time algorithm solving a given problem $X$, then $X$ can be classified in complexity class $\mathsf{P}$. There could also be a bunch of other algorithms runs in different time complexity will also be able to solve the problem with the same input size under different time complexity, i.e. exponential-time algorithms, but since there already exists a single polynomial-time algorithm accepting $X$, it is in $\mathsf{P}$.

A language is the formal realization of a problem. When we want to reason theoretically about a decision problem, we often examine the corresponding language. For a problem $X$, the corresponding language is:

A language is the formal realization of a problem. When we want to reason theoretically about a decision problem, we often examine the corresponding language. For a decision problem $X$, the corresponding language is:

Our relationship between languages and Turing Machines is as follows

1. Every Turing Machine accepts exactly one language

2. There may be more than one Turing Machine accepting a given language

3. There may be no Turing Machine that accepts a given language.

The relationship between languages and Turing Machines is as follows

1. Every Turing Machine accepts exactly one language

2. There may be more than one Turing Machine that accept a given language

3. There may be no Turing Machine that accepts a given language.