Computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.
- Abstraction100002137
- Act100030358
- Activity100407535
- Algorithm105847438
- Arrangement105726596
- Cognition100023271
- DataStructure105728493
- Event100029378
- organisation
- Procedure101023820
- PsychologicalFeature100023100
- Rule105846932
- Structure105726345
- Thing
- WikicatAlgorithms
- WikicatDataStructures
- YagoPermanentlyLocatedEntity
- Bot
- enInternetArchiveBot
- Comment
- enIn theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.
- Date
- enJanuary 2022
- Depiction
- FixAttempted
- enyes
- Has abstract
- enIn theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity. Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kinds of problems can, in principle, be solved algorithmically.
- Hypernym
- Branch
- Id
- enp/c130160
- Is primary topic of
- Computational complexity theory
- Label
- enComputational complexity theory
- Link from a Wikipage to an external page
- www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html
- www.worldscientific.com/worldscibooks/10.1142/11270%7Cdoi=10.1142/11270
- mathoverflow.net/q/34487
- www.wisdom.weizmann.ac.il/~oded/cc-book.html
- portal.acm.org/citation.cfm%3Fid=800191.805573
- complexityzoo.net/Complexity_Zoo
- people.cs.uchicago.edu/~fortnow/papers/history.pdf
- www.cs.princeton.edu/theory/complexity/
- www.scottaaronson.com/papers/philos.pdf
- Link from a Wikipage to another Wikipage
- AC (complexity)
- Adjacency list
- Adjacency matrix
- Age of the universe
- Alan Turing
- Algorithm
- ALL (complexity)
- Alphabet (computer science)
- Alternating Turing machine
- AM (complexity)
- Amortized analysis
- Analog computation
- Analysis of algorithms
- Axiom
- Best, worst and average case
- Big O notation
- Binary notation
- Biology
- Bitstring
- Blum's speedup theorem
- Blum axioms
- Blum complexity axioms
- Boolean circuit
- Boolean satisfiability problem
- Boris Trakhtenbrot
- BPP (complexity)
- BQP
- Category:Computational complexity theory
- Category:Computational fields of study
- Cellular automata
- Church–Turing thesis
- Circuit complexity
- Clay Mathematics Institute
- Cobham's thesis
- Cobham–Edmonds thesis
- Combinatorics
- Communication complexity
- Complement (complexity)
- Complete (complexity)
- Complexity
- Computability theory
- Computational complexity
- Computational complexity of mathematical operations
- Computational problem
- Computer
- Connectivity (graph theory)
- Co-NP
- Context of computational complexity
- Control theory
- Conway's Game of Life
- Cook–Levin theorem
- Counting problem (complexity)
- Decision problem
- Decision tree complexity
- Descriptive complexity theory
- Deterministic algorithm
- Deterministic Turing machine
- Differential equation
- Discrete logarithm problem
- Discrete uniform distribution
- DSPACE
- DTIME
- Dynamical system
- Euclidean algorithm
- Eugene Luks
- EXPSPACE
- EXPTIME
- Feasible solution
- File:Complexity classes.svg
- File:Complexity subsets pspace.svg
- File:Decision Problem.svg
- File:Sorting quicksort anim.gif
- File:TSP Deutschland 3.png
- File:Turing machine 2b.svg
- Formal language
- FP (complexity)
- Function problem
- Gabriel Lamé
- Game complexity
- General number field sieve
- Graph (discrete mathematics)
- Graph isomorphism
- Graph isomorphism problem
- Graph theory
- Hamiltonian path problem
- Hisao Yamada
- Information based complexity
- Integer
- Integer factorization problem
- Integer programming
- Interactive proof system
- IP (complexity)
- Jack Edmonds
- John Myhill
- Juris Hartmanis
- Knapsack problem
- L (complexity)
- Lambda calculus
- László Babai
- Leaf language
- Leonid Levin
- Limits of computation
- Linear bounded automata
- Linear time
- List of complexity classes
- List of computability and complexity topics
- List of important publications in theoretical computer science
- List of unsolved problems in computer science
- Logic gate
- Logistics
- Log-space reduction
- Manuel Blum
- Mathematical optimization
- Mathematics
- Milan
- Millennium Prize Problems
- Models of computation
- Monotone circuit
- NC (complexity)
- NEXPSPACE
- NEXPTIME
- NL (complexity)
- Non-deterministic algorithm
- Non-deterministic time
- Non-deterministic Turing machine
- NP (complexity)
- NP-complete
- NP-hard
- NP-intermediate
- NPSPACE
- NSPACE
- NTIME
- Numerical analysis
- Operations research
- Optimization problem
- P (complexity)
- Parallel computing
- Parameterized complexity
- Polynomial time
- Polynomial time hierarchy
- Polynomial-time reduction
- PP (complexity)
- Presburger arithmetic
- Primality testing
- Prime factorization
- Probabilistic Turing machine
- Probability distribution
- Promise problem
- Proof complexity
- Protein structure prediction
- PSPACE
- Pure mathematics
- P versus NP problem
- QMA
- Quantum algorithm
- Quantum complexity theory
- Quantum Turing machine
- Quicksort
- RAM machine
- Random-access machine
- Randomized algorithm
- Raymond Smullyan
- Richard E. Stearns
- Richard Karp
- RP (complexity)
- RSA (algorithm)
- SAT solver
- Savitch's theorem
- Sharp-P
- Shor's algorithm
- Space complexity
- Space hierarchy theorem
- Stephen Cook
- String (computer science)
- Structural complexity theory
- Switching theory
- Symmetric Turing machine
- Theoretical computer science
- Time complexity
- Time hierarchy theorem
- Total function
- Transcomputational problem
- Traveling salesman problem
- Turing machine equivalents
- Vertex cover problem
- Wikt:infeasible
- Wikt:intractable
- ZPP (complexity)
- SameAs
- 4120591-1
- Computational complexity theory
- Computational complexity theory
- Computationele complexiteitstheorie
- Hesaplamalı karmaşıklık teorisi
- Kompleksitetsteori
- Komplexitätstheorie
- Konplexutasun konputazionalaren teoria
- Lý thuyết độ phức tạp tính toán
- m.023z
- Q205084
- Računska teorija složenosti
- Računska teorija složenosti
- Teoria complexității
- Teoría de la complejidad computacional
- Teoría de la complexidá computacional
- Teoria de la complexitat computacional
- Teoria della complessità computazionale
- Teória zložitosti
- Teorie složitosti
- Teori kekompleksan pengiraan
- Teorya ng komputasyonal na komplehidad
- Théorie de la complexité (informatique théorique)
- woAX
- Θεωρία πολυπλοκότητας
- Теория на изчислителната сложност
- Теория сложности вычислений
- Теорија комплексности
- Теорія складності обчислень
- תורת הסיבוכיות
- نظرية التعقيد الحسابي
- نظریه پیچیدگی محاسباتی
- পরিগণনামূলক জটিলতা তত্ত্ব
- ทฤษฎีความซับซ้อนในการคำนวณ
- 計算複雑性理論
- 計算複雜性理論
- 계산 복잡도 이론
- SeeAlso
- Combinatorial explosion
- Subject
- Category:Computational complexity theory
- Category:Computational fields of study
- Thumbnail
- Title
- enComputational complexity classes
- WasDerivedFrom
- Computational complexity theory?oldid=1120968876&ns=0
- WikiPageLength
- 49963
- Wikipage page ID
- 7543
- Wikipage revision ID
- 1120968876
- WikiPageUsesTemplate
- Template:Authority control
- Template:Citation
- Template:Commonscat
- Template:ComplexityClasses
- Template:Computer science
- Template:Dead link
- Template:Div col
- Template:Div col end
- Template:Garey-Johnson
- Template:Harv
- Template:Main
- Template:Quote
- Template:Reflist
- Template:See also
- Template:Short description
- Template:Springer
- Template:Use mdy dates
- Template:Visible anchor
- Template:Wikt
