Learning Computing History

A Brief History of Algorithms and Complexity

Algorithms: a step by step procedure or instruction for solving a problem by a computer. Complexity: the resources required by the algorithms, most commonly known as the time -- how many steps it needs and the space -- how much memory it takes.  Algorithms and Complexity comprises the study of computational models, its inherent power or limitations, and the precise description of the problems to be solved. 

Data structures, graph theory and graph-theoretic algorithms, sorting and searching, shortest path and such are the building-block problems, the basic analysis are upper and average complexity bounds, or the best, average, and worst case behavior.  There are also well kwon algorithmic strategies, like Brute-Force algorithms, Greedy algorithms, Divide-and-Conquer, Backtracking, Branch-and-bound, Heuristics, numerical approximation algorithms and matrix algorithms. 

The ability for computing is simply how good the algorithm chosen and how well its implementation is. In fact, the whole computer science could be considered the study of algorithms’ formal properties, their hardware and software realizations and diverse applications.  

The Brief History of Algorithms and Complexity:

Early Algorithms, Analysis, and computability

• C. 350 B.C.E. Euclid author of the most successful mathematics book -- “Elements” and proposed his GCD (Greatest Common Divisor) algorithm
• C. 780-C. 850 Abu Ja’far Mohammed ibn Musa al-Khwarizmi composed the oldest works on arithmetic and algebra, the very name “algorism” derived from his surname.

• 1845 Lamé’s theorem: Euclid’s algorithm takes at most (4.8 log(N)/log(10) - 0.32) steps.
• 1874 Cantor developed diagonalization, and showed that in a certain sense 'almost all' numbers are transcendental
• 1900 Hilbert’s 10^th problem -- Is there a finite process which determines if a polynomial equation is solvable in integers?
• 1910 H.C. Pocklington: describes the complexity of an algorithm as polynomial on the number of bits.
• 1920 Emil L. Post first proved completeness of the classical propositional logic.

1930s started the mathematical notion of algorithms, such as recursive functions, Turing-machines, Church, Turing, post algorithmic and logical un-decidability

• 1930 Alonzo Church introduced lambda-calculus and in six year late, solved the famous decision problem – Entscheidung’s problem
• 1931 Kurt Gödel published “Gödel Incompleteness Theorems” and implies that a computer can never be programmed to answer all mathematical questions.
• 1936 Alan Turing presented the “Turing Machine”, a general model of a computing machine.
• 1947 George Dantzig  introduced simplex method

1950-60s focus was on the large scale optimization, the significance of running time for computers, the birth of computation complexity.

• 1950 Yablonski  worked on the impossibility of eliminating issue of brute-force-search
• Early 1960s, Yamada, Myhill and Smullyan all looked at time and space bounded machines
• 1964 Cobham noted the independence of polynomial-time in deterministic machine models
• 1965 Edmonds established the time complexity of a problem is polynomial or exponential,  or polynomial vs. exponential algorithms
• 1965 Juris Hartmanis and Richard Stearns established the foundations of computational complexity theory and theoretical computer science as a whole.

1960-80s, the growth of complexity theory, included time, space information complexity, Non-determinism, completeness, polynomial hierarchy, classification of P vs. NP-complete, Parallelism and Randomization.

• 1950s-1970s P=NP? question had drawn much of the attentions
  • P the set of decision problems that can be solved by a deterministic machine in polynomial time
  • NP the set of decision problems that can be solved by a non-deterministic machine in polynomial time.
• 1971 Stephen Cook’s Theorem showed that any NP problem can be converted in polynomial time to the specific problem SAT.
• 1971 Richard Karp proved eight central combinatorial problems are all NP-complete. Karp reductions--many to one reduction.
• 1972 Meyer and Stockmeyer defined the polynomial-time hierarchy
• 1972 Borodin and Trakhtenbrot (1964) independently proved the gap theorem
• 1973 Levin Search one of the few speed up algorithms for universal sequential search problems
• 1975 Baker, Gill, Solovay all worked on relativization: there exists oracles A and B such that P^A = NP^A and P^B¹ NP^B
• 1975 Ladner claimed that every language in P has a polynomial size circuits
• 1979 Khachyan showed that the ellipsoid method is a polynomial-time algorithm.
• 1980 Savitch’s Theorem showed how to convert the nondeterministic polynomial
  space algorithm into a deterministic polynomial space algorithm
• 1982 Richard Feynman suggested the possibility that computers built on quantum mechanics
• 1984 Narendra Karmakar interior point algorithms
• 1985 David Deutch developed a theoretical computation model  based on quantum mechanics
• 1986 Hastad introduced “Switching lemma” and  bounds for parity

1990s upper and lower bounds on complexity with the increasing sophistication, the rise of new models, like quantum computers and propositional proof system.

• Max Cut Problem: “Given an undirected graph with edge weights, the MAX-CUT problem consists in finding a partition of the nodes into two subsets, such that the sum of the weights of the edges having endpoints in different subsets is maximized.” -- Randomized heuristics for the max-cut problem, P. Festa et al.
• Quantum Computer: “ a machine that performs calculations based on the laws of quantum mechanics, which is the behavior of particles at the sub-atomic level” – Joseph Stelmach
• 1994 Peter Shor came up with a quantum algorithm for factoring integers in polynomial time.
• 1995 Peter Blum’s abstract complexity measure discussed union, speed-up and gap theorems, holds not only for time but also space.
• 1997 Lov Grover  introduced a quantum search algorithm with O(√N) complexity
• 1997 Bernstein and Vazirani  gave formal definition of the class BQP

Summary:  Algorithms and computation complexity had evolved forty good years, will someone show that P = NP? Or will an unexpected connection be there somewhere? Will you are the next one that surprises everybody?  Be ready!