# 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. 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 decision 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. 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). 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. 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. 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 Mar 31 '17 at 7:03

Even more TLDR:

Problem: Given an input return an output related to the input in some way. Decision problems answer yes/no questions related to the input Optimization problems seek to minimize or maximize some property related to the input. Algorithm: a specific instance of solving a problem. Problems may have many algorithms that solve the problem Language: formalization of the problem (in decision format). That is, the set of all strings spelled from an alphabet for which the problem is true (in the case of a decision problem).

• Welcome to COMPUTER SCIENCE @SE. Append two blanks to lines you want a break after, e.g. Algorithm:  Oct 5 at 11:08