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?

  • $\begingroup$ An algorithm is a way to solve a problem. $\endgroup$ Commented Dec 11, 2014 at 12:13

2 Answers 2


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

  • 1
    $\begingroup$ Please feel free to edit this answer as you see fit. $\endgroup$ Commented Aug 8, 2013 at 6:16
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Mar 20, 2014 at 3:09
  • 5
    $\begingroup$ Dude, this is the greatest answer I've ever seen. You just summarized all of computer science in 1 page. $\endgroup$ Commented Jan 2, 2016 at 21:44
  • 1
    $\begingroup$ NP isn't really about the time complexity of solving a problem; it says (roughly) that a solution can be verified in polynomial time. NP and co-NP are very different, but take exactly the same time to solve. $\endgroup$
    – gnasher729
    Commented Mar 30, 2017 at 18:26
  • 1
    $\begingroup$ @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 $\endgroup$ Commented Mar 31, 2017 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).

  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. Append two blanks to lines you want a break after, e.g. Algorithm: $\endgroup$
    – greybeard
    Commented Oct 5, 2021 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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