Computational Complexity Theory
Full Title or Meme
The meta-mathematics of determining how hard it is to solve a problem. This originally was just complexity theory, but that has recently become more complex and includes other specialties/
Another major contributor to complexity theory is John Holland, a computer scientist and professor at the University of Michigan. Holland designed the genetic algorithm based on the idea that components of complex systems can be broken down into building blocks, whose characteristics can then be represented in code.
Context
- The wiki page on Complexity begins to address Complexity from a computation point of view.
- This page is interesting for the relationship to Business
Between 1500–1700, there was an important and dramatic shift in the way that people in Europe perceived and understood the world. Through the works of thinkers such as Francis Bacon, Galileo Galilei, Johannes Kepler, Rene Descartes, and Isaac Newton, the Western world underwent a scientific revolution. This resulted in a shift from a worldview governed by the Church and Christian theology and ethics, to that of an inanimate, machine-like material world governed by natural forces and exact mathematical rules.[1]
David Hilbert proposed in 1900 his challenge #2 to prove the consistency of the axioms of arithmetic for logical problems. Kurt Gödel showed that this was not possible in 1931.[2] This discovery was just a few years after Heisenberg showed that the mathematics of Quantum Mechanics asserted a fundamental limit to the accuracy of any measurements made on an individual quantum particle. Finally in 1996 Ilya Prigogine published a book declaring "The End of Certainty."[3]
Here is just one tip of the iceberg we’ll explore in this book: How much time does it take to find the prime factors of a 1,000-digit integer? The facts are that (1) we can’t even roughly estimate the answer: it could be less than a second or more than a million years, and (2) practically all electronic commerce and Internet security systems in existence today rest on the belief that it takes more than a million years![4]
References
- ↑ Capra and Luisi, The Newtonian world-machine. In The Systems View of Life: A Unifying Vision (pp. 19–34). Cambridge: Cambridge University Press. (2014) doi:10.1017/CBO9780511895555.004
- ↑ Kurt Gödel, On Formally Undecidable Propositions of Principia Mathematica and Related Systems Dover (original in German 1931) ISBN 9780486669809
- ↑ Ilya Prigogine, The End of Certainty, Free Press (1996) ISBN 0684837059
- ↑ Avi Wigderson, Mathematics and Computation Princeton UP 2019 https://www.math.ias.edu/files/Book-online-Aug0619.pdf#page=1
Other Material
- See wiki page on Information in Physics
