13
$\begingroup$

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 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. I was not able to find any related article predating 1960 (using Google Scholar).

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"?

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Kaveh Mar 15 '12 at 23:17
5
$\begingroup$

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 contains a nice historical description of this phrase with many references.

$\endgroup$
  • $\begingroup$ Thanks Tyson, that looks like an interesting paper (but doesn't seem to answer my questions). $\endgroup$ – Kaveh Mar 15 '12 at 2:01
3
$\begingroup$

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 Niel de Beaudrap mentions in the comments, Gauss already discussed the (in)efficiency of algorithms for primality testing in his 1801 Disquisitiones Arithmeticae, 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.]

$\endgroup$
  • 2
    $\begingroup$ There was also an answer on another topic, 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". $\endgroup$ – Niel de Beaudrap Aug 5 '12 at 8:10
  • $\begingroup$ 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"). $\endgroup$ – Kaveh Aug 6 '12 at 4:13
  • $\begingroup$ 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}$. $\endgroup$ – Kaveh Aug 6 '12 at 4:18
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am looking for actual history of these terms, not an explanation for them. This is not an answer to my question. $\endgroup$ – Kaveh Aug 3 '12 at 21:30
  • $\begingroup$ 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. $\endgroup$ – labotsirc Aug 3 '12 at 21:52
  • $\begingroup$ Thanks, but I am not asking "why", I am asking "how" (i.e. history). $\endgroup$ – Kaveh Aug 3 '12 at 21:54
  • $\begingroup$ i've re-written the answer, this is all i know + suppositions. Regards, Cristobal. $\endgroup$ – labotsirc Aug 3 '12 at 22:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Aug 3 '12 at 22:07

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.