Fields
Algorithms and Complexity Theory
Also Known As Computational Complexity Theory
Citation Formats
General Reference
APA Style
BibTeX
Algorithms and Complexity Theory studies what can be computed, how efficiently it can be computed, and how to prove the answer. It gives every other field of computing its shared vocabulary of running time, correctness and provable limits, from Euclid's algorithm for the greatest common divisor through to the sorting and searching algorithms taught in every introductory course. Its central practical question is how the resources an algorithm needs, most often time and memory, grow as the size of its input grows, and its central theoretical question is which problems admit an efficient algorithm at all.
Facts
Disputed
Origin Year1936
Informal algorithms are ancient, Euclid's algorithm dates to around 300 BCE, but the field as a distinct mathematical discipline is usually dated to 1936, when Alan Turing and, independently, Alonzo Church gave the first formal definitions of what it means for a procedure to be computable at all. Core ConcernWhat can be computed at all, how efficiently a solution can be found, and how to prove a bound on that efficiency. 1 Cross-Tradition Connections
Sources
1. IEEE Annals of the History of Computing
1. IEEE Annals of the History of Computing
Encyclopedia Britannica: Computer Science
Encyclopedia Britannica Editors, Encyclopaedia Britannica Inc, 2024View the Source Alan Turing: The Enigma
Andrew Hodges, Burnett Books, 1983Includes: Alan Turing
Alan Turing: The Enigma
Andrew Hodges, Burnett Books, 1983Includes: Turing Machine
The Innovators: How a Group of Hackers, Geniuses, and Geeks Created the Digital Revolution
Walter Isaacson, Simon and Schuster, 2014Includes: Ada Lovelace
Wikipedia: Big O Notation
Wikipedia: NP-completeness
Wikipedia: Dynamic Programming
Wikipedia: Stack (Abstract Data Type)
Wikipedia: Queue (Abstract Data Type)
Wikipedia: Depth-First Search
Wikipedia: P versus NP Problem
Wikipedia: Quantum computing
Wikimedia FoundationAssociated With: Quantum Computing, Lead sectionQuote, Associated With: Quantum Computing, Lead section
A quantum computer is a computer that represents and processes information using quantum states.
Wikipedia: Merge sort
Wikipedia: Binary search tree
Wikimedia FoundationIncludes: Binary Search Tree, History sectionView the Source Open Questions (1 open question)
Does P equal NP?
The P versus NP problem is a major unsolved problem in theoretical computer science: it asks whether every decision problem whose proposed positive answer can be quickly verified can also be quickly solved. Stephen Cook introduced its precise statement in 1971, and despite half a century of effort nobody has proved the classes equal or unequal; it is one of the seven Millennium Prize Problems, with a one million dollar prize for the first correct solution.
What would resolve this A proof that every problem in NP admits a polynomial time algorithm, or a proof that some NP problem admits none. Either direction would be among the most consequential results in the history of mathematics and computing.
Computational complexity theory, MathematicsWikipedia: P versus NP Problem
Reader Challenges (0 open reader challenges)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.
View At A Past Year
The atlas records no dated fact of its own for this entry, so there is no other year to choose.