# What is the difference between an algorithm, a language and a problem?

It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and considering problems? And how do these relate to the concept of a language in formal language theory?

• An algorithm is a way to solve a problem. – reinierpost Dec 11 '14 at 12:13

For simplicity, I'll begin by only considering "decision" problems, which have a yes/no answer. Function problems work roughly the same way, except instead of yes/no, there is a specific output word associated with each input word.

Language: a language is simply a set of strings. If you have an alphabet, such as $\Sigma$, then $\Sigma^*$ is the set of all words containing only the symbols in $\Sigma$. For example, $\{0,1 \}^*$ is the set of all binary sequences of any length. An alphabet doesn't need to be binary, though. It can be unary, ternary, etc.

A language over an alphabet $\Sigma$ is any subset of $\Sigma^*$.

Problem: A problem is some question about some input we'd like answered. Specifically, a decision problem is a question which asks, "Does our given input fulfill property $X$?

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:

$L = \{w \mid w$ is the encoding of an input $y$ to problem $X$, and the answer to input $y$ for problem $X$ is "Yes" $\}$

Determining if the answer for an input to a decision problem is "yes" is equivalent to determining whether an encoding of that input over an alphabet is in the corresponding language.

Algorithm: An algorithm is a step-by-step way to solve a problem. Note that there an algorithm can be expressed in many ways and many languages, and that there are many different algorithms solving any given problem.

Turing Machine: A Turing Machine is the formal analogue of an algorithm. A Turing Machine over a given alphabet, for each word, either will or won't halt in an accepting state. Thus for each Turing Machine $M$, there is a corresponding language:

$L(M) = \{w \mid M$ halts in an accepting state on input $w\}$.

(There's a subtle difference between Turing Machines that halt on all inputs and halt on yes inputs, which defines the difference between complexity classes $\mathsf{R}$ and $\mathsf{RE}$.)

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.

We can say roughly the same thing about algorithms and problems: every algorithm solves a single problem, but there may be 0, or many, algorithms solving a given problem.

Time Complexity: One of the most common sources of confusion between algorithms and problems is in regards to complexity classes. The correct allocation can be summarized as follows:

• An algorithm has a time complexity
• A problem belongs to a complexity class

An algorithm can have a certain time complexity. We say an algorithm has a worst-case upper-bounded complexity $f(n)$ if the algorithm halts in at most $f(n)$ steps for any input of size $n$.

Problems don't have run-times, since a problem isn't tied to a specific algorithm which actually runs. Instead, we say that a problem belongs to a complexity class, if there exists some algorithm solving that problem with a given time complexity.

$\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}$.

• Please feel free to edit this answer as you see fit. – jmite Aug 8 '13 at 6:16
• I think it would be good to mention that there are other kinds of computational problems (e.g. search problems). – Kaveh Aug 18 '13 at 9:43
• Says who? That kind of thinking is part of why people had so much trouble formalizing and algorithm before the intention of the Turing Machine. The Church-Turing Thesis says that an algorithm IS a turing machine and vice versa, and not all turing machines halt. – jmite Mar 20 '14 at 3:09
• Dude, this is the greatest answer I've ever seen. You just summarized all of computer science in 1 page. – CaptainCodeman Jan 2 '16 at 21:44
• @gnasher729 there's a theorem that says it can be defined in terms of verifying, but it's actual definition is in terms of time complexity for Non deterministic machines, thus the name NP: nondeterministic polynomial – jmite Mar 31 '17 at 7:03