[Solved]: When did polynomial-time algorithm become of interest?

Problem Detail: I would like to understand why and when polynomial algorithms became of interest. When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when the concept of an algorithm was discovered, or the the term algorithm used. For instance, I’ve looked at some textbook of Algorithms such as the one by Cover, Leiserson, Rivest, and Stein “Introduction to Algorithms” 3rd ed. they states in the Preface “Before there were computers, there were algorithms. But now that there are computers, there are even more algorithms, and algorithms lie at the heart of computing”. Would it be the case that, before computers were invented, we were more interested in finding new ideas for solving problems, and were not so concerned with the time it took. So I am interested in knowing when people became conscious of the importance of efficiency, started to study it more systematically. Are there some reference papers on the subject, on the history of algorithms and their motivations, and on the concern with efficiency. [note from the translator] The topic of the question may seem a bit wide, as I tried to keep the meaning without betraying the author. But it seems a good and useful general question that can be adressed with a few general remarks and some facts and examples

Asked By : user777

Answered By : hengxin

Since this question was reopened and made more explicit, I would like to convert my comment into an answer. Now the OP wants to understand

why and when polynomial algorithms became of interest.

I especially focus on the sub-question:

When did people realize the role and importance of efficient versus non-efficient algorithms?

Because algorithms, in its general terms, have existed since ancient times, it is hard to identify the person who is the first to highly praise the polynomial algorithms(, and when and why). However, there is a famous person who has explicitly advocated the polynomial algorithms. It is Jack Edmonds, in the paper Paths, Trees, and Flowers; 1965. In Introduction, the author claims

We describe an efficient algorithm for finding in a given graph a matching of maximum cardinality.

Then in the second section titled “Digression”, the author

An explanation is due on the use of the words “efficient algorithm”.

Then come the explanations:

There is an obvious finite algorithm, but that algorithm increases in difficulty exponentially with the size of the graph. It is by no means obvious whether or not there exists an algorithm whose difficulty increases only algebraically with the size of the graph. When the measure of problem-size is reasonable and when the sizes assume values arbitrarily large, an asymptotic estimate of $ldots$ the order of difficulty of an algorithm is theoretically important. For practical purposes the difference between algebraic and exponential order is often more crucial than the difference between finite and non-finite. However, if only to motivate the search for good, practical algorithms, it is important to realize that it is mathematically sensible even to question their existence. For one thing the task can then be described in terms of concrete conjectures.

ADDED: I have just happened to found a third-party confirmation that it was Jack Edmonds who originally advocated the polynomial algorithms. The following is quoted from Section 2.18.1 of the book “Applied Combinatorics (second edition)” by Fred Roberts and Barry Tesman.

A generally accepted principle is that an algorithm is good if it is polynomial. This idea is originally due to Edmonds [1965].

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43740 Ask a Question Download Related Notes/Documents