<p>Another phrase to consider is "exactly solvable", which is from statistical physics and also corresponds with our present-day notions of efficient/feasible. The introduction in <a href="http://arxiv.org/abs/1008.0683">this paper</a> contains a nice historical description of this phrase with many references.</p>

CC BY-SA 3.0
2012-03-15T02:01:54.590Z
Thanks Tyson, that looks like an interesting paper (but doesn't seem to answer my questions).
Kaveh
CC BY-SA 3.0
2012-03-15T01:52:39.133Z
2012-03-15T01:52:39.133Z
Tyson Williams
<p>This isn't exactly what you asked for, but it's too long for a comment.</p>
<p>The oldest explicit reference I know to an algorithm being <em>infeasible</em> is in Évariste Galois' <em>Mémoire sur les conditions de résolubilité des équations par radicaux</em>, written in 1830:</p>
<blockquote>
<p>Si maintenant vous me donnez une équation que vous aurez choisie à
votre gré et que vous desirez connaître si elle est ou non soluble
par radicaux, je n’aurais rien à y faire que de vous indiquer le
moyen de répondre à votre question, sans vouloir charger ni moi ni
personne de la faire. En un mot les calculs sont <strong>impracticables.</strong></p>
<p>[Now if you give me an equation that you have chosen at your
discretion and you want to know whether or not it is solvable by
radicals, I need only to indicate to you the method needed to answer
your question, without wanting to make myself or anyone else carry it
out. In a word, the calculations are <strong>impractical</strong>.]</p>
</blockquote>
<p>Although it's <em>true</em> that Galois' algorithm doesn't run in polynomial time, Galois clearly meant something much less precise.  This is also the oldest reference I know of that considers the mere <em>existence</em> of an algorithm significant in its own right.</p>
<hr />
<p>As Niel de Beaudrap mentions in the comments, Gauss already discussed the (in)efficiency of algorithms for primality testing in his 1801 <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN235993352&amp;IDDOC=137206" rel="nofollow noreferrer"><em>Disquisitiones Arithmeticae</em></a>, almost 30 years before Galois.  For completeness, here is the relevant passage from article 329:</p>
<blockquote>
<p>Nihilominus fateri oportet, omnes methodos hucusque prolata vel ad casus vlade speciales restrictas esse, vel <strong>tam operosas et prolixas</strong>, ut iam pro numeris talibus, qui tabularum a varis meritis constructarum limites non excedunt, <em>i.e.</em> pro quibus methodi artificiales supervacuae sunt, calculatoris etiam exercitati patientiam fatigent, ad maiores autem plerumque vix applicari possint. ... Ceterum in problematis natura fundatum est, ut methodi <em>quaecunque</em> continuo prolixiores evadant, quo maiores sunt numeri, ad quos applicantur; attamen pro methodis sequentibus difficultates perlente increscunt, numerique e septem, octos vel adeo adhuc pluribus figuris constantes praesertim per secundam felici semper successu tractati fuerunt, omnique celeritate, quam pro tantis numeris exspectare aequum est, qui secundum omnes methodos hactenus notas <strong>laborem, etiam calculatori indefatigabili intolerabilem,</strong> requirerent.</p>
<p>[Nevertheless we must confess that all methods that have been proposed thus far are either restricted to very special cases or are <strong>so laborious and prolix</strong> that even for numbers that do not exceed the limits of tables constructed by estimable men, <em>i.e.</em> for numbers that do not require ingenious methods, they try the patience of even the most practiced calculator.  And these methods can hardly be used for larger numbers. ... It is in the nature of the problem that <em>any</em> method will become more prolix as the numbers to which it is applied grow larger.  Nevertheless, in the following methods the difficulties increase rather slowly, and numbers with seven, eight, or even more digits have been handled with success and speed beyond expectation, especially by the second method.  The techniques that were previously known would require <strong>intolerable labor even for the most indefatigable calculator</strong>.]</p>
</blockquote>

CC BY-SA 3.0
2012-08-05T08:10:24.530Z
There was also an [answer on another topic](http://cstheory.stackexchange.com/a/1908/248), on the oldest open research problems, in which Gauss complained in his 1801 book *Disquitiones Arithmeticae* that all methods known at the time for primality testing were very "laborious and prolix".
Niel de Beaudrap
CC BY-SA 3.0
2012-08-06T04:13:48.763Z
Thanks Jeff. Page 14 of Rudich and Wigderson's book, "Computational Complexity Theory", 2004, also has a nice table about the history of complexity from 1950s. They also mention Euclid's GCD algoritm in addition to Gauss. Rudich writes on page 8 that Gauss also explicitly formulated the question of finding a much faster algorithm for finding a generator for $\mathbb{Z}^*_p$  (calling it "an algorithm in better taste").
Kaveh
CC BY-SA 3.0
2012-08-06T04:18:17.807Z
However I am mainly interested in how "efficiency" and "feasibility" become synonymous in 20th century complexity theory. Especially algorithmic efficiency in the sense of $\mathsf{P}$.
Kaveh
CC BY-SA 3.0
2012-08-03T22:07:52.083Z
2012-08-05T19:02:44.720Z
2020-06-17T09:38:08.363Z
Jeffε
<p>Edit: Answer re-written </p>

<p>How it got mainstream? probably by spreading the idea of comparing new research with older one in terms of performance, with the supposition that creating new ideas is more difficult.</p>

CC BY-SA 3.0
2012-08-03T21:30:08.370Z
I am looking for actual history of these terms, not an explanation for them. This is not an answer to my question.
Kaveh
CC BY-SA 3.0
2012-08-03T21:52:50.197Z
I cannot answer who used the terms for the first time in CS, my answer was more oriented to your second question regarding why it got mainstream.
labotsirc
CC BY-SA 3.0
2012-08-03T21:54:44.690Z
Thanks, but I am not asking "why", I am asking "how" (i.e. history).
Kaveh
CC BY-SA 3.0
2012-08-03T22:05:15.907Z
i've re-written the answer, this is all i know + suppositions. Regards, Cristobal.
labotsirc
CC BY-SA 3.0
2012-08-03T22:07:26.060Z
Thanks axis, but as I said I am looking for *actual* history, not probable theories about it. I am looking for early references/papers/... that have used the terms and helped it become mainstream.
Kaveh
CC BY-SA 3.0
2012-08-03T20:35:26.620Z
2012-08-03T22:03:51.603Z
2012-08-03T22:03:51.603Z
labotsirc
<p>I don't know about the terms "efficient" and "feasible."  Since these terms even today have no precise technical meaning, I suspect that the history of their usage will turn out to be murky, just as the history of most words in most languages is murky.</p>

<p>"Computational complexity" is a more interesting term.  With the help of MathSciNet, I find that Juris Hartmanis seems to have been the first to popularize it.  The famous 1965 paper by Hartmanis and Stearns uses the term in the title, but even before that, Hartmanis's Mathematical Review of Michael Rabin's paper "Real time computation" (<i>Israel J. Math.</i> <b>1</b> (1963), 203–211) says:</p>

<blockquote>
  <p>This result is very instructive and contributes new techniques to the emerging theory of computational complexity of recursive sequences and functions. This theory is mainly concerned with the classification of computable problems by their degree of computational difficulty, the study of the properties of these complexity classes, their relation to each other and their dependence on the (abstract) computing devices.</p>
</blockquote>

<p>Note that Rabin himself does <i>not</i> use the term "computational complexity" in this paper.</p>

<p>MathSciNet also turns up a couple of earlier reviews that use the term "computational complexity," but these seem to be spontaneous and sporadic occurrences.</p>

CC BY-SA 3.0
2012-03-15T23:17:09.030Z
Thanks, I think this answers my question about "computational complexity". (I would like to wait a few more days to see if someone  can provide some information about the first two terms.)
Kaveh
CC BY-SA 3.0
2012-03-15T14:39:29.130Z
2012-03-15T14:39:29.130Z
Timothy Chow
<p>I would like to know about the history of these two terms: "<strong>efficient</strong>", "<strong>feasible</strong>". </p>

<p>Who used them about computation/algorithms the first time? (in modern sense of these terms, i.e. 20th century).
How did they become mainstream? 
How did these two terms start to be used as synonyms?</p>

<p>I know that Cobham used the term "feasible" in the statement of <a href="http://en.wikipedia.org/wiki/Cobham%27s_thesis">his thesis</a> which associated with polynomial time computability. But is there an earlier reference? There doesn't seem to be an explicit reference to these terms in <a href="http://rjlipton.wordpress.com/the-gdel-letter/">Godel's letter to von Neumann</a>. I was not able to find any related article predating 1960 (using <a href="http://scholar.google.com/">Google Scholar</a>).</p>

<p>Another interesting point is that the title of Cobham's paper from 1965 is "The intrinsic <strong>computational difficulty</strong> of functions". When did "computational complexity" replace "computational difficulty"?</p>

<cc.complexity-theory><ds.algorithms><ho.history-overview>
The origin of the terms "efficient" and "feasible" computation/algorithm
Kaveh
# The origin of the terms "efficient" and "feasible" computation/algorithm

(Asked by: username_0 on 2012-03-12)

I would like to know about the history of these two terms: "**efficient**", "**feasible**".

Who used them about computation/algorithms the first time? (in modern sense of these terms, i.e. 20th century).
How did they become mainstream?
How did these two terms start to be used as synonyms?

I know that Cobham used the term "feasible" in the statement of [his thesis](http://en.wikipedia.org/wiki/Cobham%27s_thesis) which associated with polynomial time computability. But is there an earlier reference? There doesn't seem to be an explicit reference to these terms in [Godel's letter to von Neumann](http://rjlipton.wordpress.com/the-gdel-letter/). I was not able to find any related article predating 1960 (using [Google Scholar](http://scholar.google.com/)).

Another interesting point is that the title of Cobham's paper from 1965 is "The intrinsic **computational difficulty** of functions". When did "computational complexity" replace "computational difficulty"?

**Tags:** cc.complexity-theory, ds.algorithms, ho.history-overview


---

## 4 answers

### Answer by username_5 on 2012-03-15. Score: 11 | Accepted answer

I don't know about the terms "efficient" and "feasible." Since these terms even today have no precise technical meaning, I suspect that the history of their usage will turn out to be murky, just as the history of most words in most languages is murky.

"Computational complexity" is a more interesting term. With the help of MathSciNet, I find that Juris Hartmanis seems to have been the first to popularize it. The famous 1965 paper by Hartmanis and Stearns uses the term in the title, but even before that, Hartmanis's Mathematical Review of Michael Rabin's paper "Real time computation" (*Israel J. Math.* **1** (1963), 203–211) says:

> This result is very instructive and contributes new techniques to the emerging theory of computational complexity of recursive sequences and functions. This theory is mainly concerned with the classification of computable problems by their degree of computational difficulty, the study of the properties of these complexity classes, their relation to each other and their dependence on the (abstract) computing devices.

Note that Rabin himself does *not* use the term "computational complexity" in this paper.

MathSciNet also turns up a couple of earlier reviews that use the term "computational complexity," but these seem to be spontaneous and sporadic occurrences.

> **Comments:**
> **username_0**: Thanks, I think this answers my question about "computational complexity". (I would like to wait a few more days to see if someone  can provide some information about the first two terms.)  

---

### Answer by username_1 on 2012-03-15. Score: 5

Another phrase to consider is "exactly solvable", which is from statistical physics and also corresponds with our present-day notions of efficient/feasible. The introduction in [this paper](http://arxiv.org/abs/1008.0683) contains a nice historical description of this phrase with many references.

> **Comments:**
> **username_0**: Thanks Tyson, that looks like an interesting paper (but doesn't seem to answer my questions).  

---

### Answer by username_2 on 2012-08-03. Score: 3

This isn't exactly what you asked for, but it's too long for a comment.

The oldest explicit reference I know to an algorithm being *infeasible* is in Évariste Galois' *Mémoire sur les conditions de résolubilité des équations par radicaux*, written in 1830:

> Si maintenant vous me donnez une équation que vous aurez choisie à
> votre gré et que vous desirez connaître si elle est ou non soluble
> par radicaux, je n’aurais rien à y faire que de vous indiquer le
> moyen de répondre à votre question, sans vouloir charger ni moi ni
> personne de la faire. En un mot les calculs sont **impracticables.**
>
> [Now if you give me an equation that you have chosen at your
> discretion and you want to know whether or not it is solvable by
> radicals, I need only to indicate to you the method needed to answer
> your question, without wanting to make myself or anyone else carry it
> out. In a word, the calculations are **impractical**.]

Although it's *true* that Galois' algorithm doesn't run in polynomial time, Galois clearly meant something much less precise. This is also the oldest reference I know of that considers the mere *existence* of an algorithm significant in its own right.

---

As username_3 mentions in the comments, Gauss already discussed the (in)efficiency of algorithms for primality testing in his 1801 [*Disquisitiones Arithmeticae*](http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN235993352&IDDOC=137206), almost 30 years before Galois. For completeness, here is the relevant passage from article 329:

> Nihilominus fateri oportet, omnes methodos hucusque prolata vel ad casus vlade speciales restrictas esse, vel **tam operosas et prolixas**, ut iam pro numeris talibus, qui tabularum a varis meritis constructarum limites non excedunt, *i.e.* pro quibus methodi artificiales supervacuae sunt, calculatoris etiam exercitati patientiam fatigent, ad maiores autem plerumque vix applicari possint. ... Ceterum in problematis natura fundatum est, ut methodi *quaecunque* continuo prolixiores evadant, quo maiores sunt numeri, ad quos applicantur; attamen pro methodis sequentibus difficultates perlente increscunt, numerique e septem, octos vel adeo adhuc pluribus figuris constantes praesertim per secundam felici semper successu tractati fuerunt, omnique celeritate, quam pro tantis numeris exspectare aequum est, qui secundum omnes methodos hactenus notas **laborem, etiam calculatori indefatigabili intolerabilem,** requirerent.
>
> [Nevertheless we must confess that all methods that have been proposed thus far are either restricted to very special cases or are **so laborious and prolix** that even for numbers that do not exceed the limits of tables constructed by estimable men, *i.e.* for numbers that do not require ingenious methods, they try the patience of even the most practiced calculator. And these methods can hardly be used for larger numbers. ... It is in the nature of the problem that *any* method will become more prolix as the numbers to which it is applied grow larger. Nevertheless, in the following methods the difficulties increase rather slowly, and numbers with seven, eight, or even more digits have been handled with success and speed beyond expectation, especially by the second method. The techniques that were previously known would require **intolerable labor even for the most indefatigable calculator**.]

> **Comments:**
> **username_3**: There was also an [answer on another topic](http://cstheory.stackexchange.com/a/1908/248), on the oldest open research problems, in which Gauss complained in his 1801 book *Disquitiones Arithmeticae* that all methods known at the time for primality testing were very "laborious and prolix".  
> **username_0**: Thanks Jeff. Page 14 of Rudich and Wigderson's book, "Computational Complexity Theory", 2004, also has a nice table about the history of complexity from 1950s. They also mention Euclid's GCD algoritm in addition to Gauss. Rudich writes on page 8 that Gauss also explicitly formulated the question of finding a much faster algorithm for finding a generator for $\mathbb{Z}^*_p$  (calling it "an algorithm in better taste").  
> **username_0**: However I am mainly interested in how "efficiency" and "feasibility" become synonymous in 20th century complexity theory. Especially algorithmic efficiency in the sense of $\mathsf{P}$.  

---

### Answer by username_4 on 2012-08-03. Score: -1

Edit: Answer re-written

How it got mainstream? probably by spreading the idea of comparing new research with older one in terms of performance, with the supposition that creating new ideas is more difficult.

> **Comments:**
> **username_0**: I am looking for actual history of these terms, not an explanation for them. This is not an answer to my question.  
> **username_4**: I cannot answer who used the terms for the first time in CS, my answer was more oriented to your second question regarding why it got mainstream.  
> **username_0**: Thanks, but I am not asking "why", I am asking "how" (i.e. history).  
> **username_4**: i've re-written the answer, this is all i know + suppositions. Regards, Cristobal.  
> **username_0**: Thanks axis, but as I said I am looking for *actual* history, not probable theories about it. I am looking for early references/papers/... that have used the terms and helped it become mainstream.  

---

