40
$\begingroup$

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?

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

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

$\endgroup$
  • 1
    $\begingroup$ Please feel free to edit this answer as you see fit. $\endgroup$ – jmite Aug 8 '13 at 6:16
  • $\begingroup$ I think it would be good to mention that there are other kinds of computational problems (e.g. search problems). $\endgroup$ – Kaveh Aug 18 '13 at 9:43
  • 1
    $\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$ – jmite Mar 20 '14 at 3:09
  • 4
    $\begingroup$ Dude, this is the greatest answer I've ever seen. You just summarized all of computer science in 1 page. $\endgroup$ – CaptainCodeman Jan 2 '16 at 21:44
  • 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$ – jmite Mar 31 '17 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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