Field
Algorithms and Complexity Theory
Also Known As Computational Complexity Theory
Theory Of Computation
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 Algorithms and Complexity Theory
Filter Results4 entries
Connections
Associated With
Field-to-field association; both are standard neighbouring areas of computing
Computer algebra is defined by Wikipedia as the study and development of algorithms for manipulating mathematical expressions, placing it alongside the atlas's algorithms and complexity theory field.
Source Computer Algebra (Wikipedia)
DNA Computing, Fields Field-to-field association; both are standard neighbouring areas of computing
Source Wikipedia: Quantum computing
Includes
Source The Innovators: How a Group of Hackers, Geniuses, and Geeks Created the Digital RevolutionWalter Isaacson
Source Alan Turing: The EnigmaAndrew Hodges
Source Encyclopedia Britannica: Computer ScienceEncyclopedia Britannica Editors
Source Wikipedia: Big O notation
Source Wikipedia: Binary search tree
Source Wikipedia: Depth-First Search
Source Wikipedia: Dynamic Programming
Source Encyclopedia Britannica: Computer ScienceEncyclopedia Britannica Editors
Source Wikipedia: Merge sort
Source Wikipedia: NP-completeness
Source Wikipedia: P versus NP Problem
Source Wikipedia: Queue (Abstract Data Type)
Source Encyclopedia Britannica: Computer ScienceEncyclopedia Britannica Editors
Source Wikipedia: Stack (Abstract Data Type)
Source Alan Turing: The EnigmaAndrew Hodges
Long-Form Articles
Open Questions
Source Wikipedia: P versus NP Problem
Sources
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, 1983- Includes: Alan Turing
- Includes: 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 Computer Algebra (Wikipedia)
Wikimedia FoundationAssociated With: Computer Algebra, Lead sectionQuote, Associated With: Computer Algebra, Lead section
Computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating mathematical expressions.
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)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.