Category:Computational complexity theory

A

• Analysis of algorithms‎ (3 C, 49 P)

C

• Circuit complexity‎ (19 P)
• Complexity classes‎ (1 C, 92 P)
• Computational resources‎ (13 P)

D

• Descriptive complexity‎ (12 P)

M

• Measures of complexity‎ (1 C, 15 P)

N

• NP-complete problems‎ (87 P)

P

• Parameterized complexity‎ (1 C, 7 P)

Q

• Quantum complexity theory‎ (18 P)
• Quantum computing‎ (3 C, 91 P)

S

• Structural complexity theory‎ (1 C, 20 P)

T

• Theorems in computational complexity theory‎ (21 P)

• Computational complexity theory

*

• Complexity class
• Padding argument

A

• Aanderaa–Karp–Rosenberg conjecture
• Advice (complexity)
• Analysis of algorithms
• Approximation algorithm
• Asymptotic computational complexity
• Averaging argument

B

• Bernstein–Vazirani algorithm
• Best, worst and average case
• Boolean circuit

C

• Certificate (complexity)
• Circuit complexity
• Circuits over sets of natural numbers
• Claw finding problem
• Cobham's thesis
• Combinatorial optimization
• Combinatorial search
• Communication complexity
• Complement (complexity)
• Complete (complexity)
• Complexity and Real Computation
• Complexity index
• The Complexity of Songs
• Compression theorem
• Computable topology
• Computation tree
• Computational complexity
• Computational complexity of mathematical operations
• Computational complexity of matrix multiplication
• Configuration graph
• Computational resource
• Computational topology
• Computationally bounded adversary
• Computing the permanent
• Constructible function
• Context of computational complexity

D

• Decision tree model
• Descriptive complexity theory
• Dynamic problem (algorithms)

E

• Effective complexity
• Electronic Colloquium on Computational Complexity
• Exact algorithm
• Existential theory of the reals

F

• Folded Reed–Solomon code

G

• Gadget (computer science)
• Games, Puzzles, and Computation
• Gap-Hamming problem
• Generalized game
• Generic-case complexity
• Geometric complexity theory
• Glossary of quantum computing
• Graph isomorphism problem

H

• Half-exponential function
• Hamiltonian complexity
• Hardness of approximation
• Hidden linear function problem

I

• Implicit computational complexity
• Information-based complexity
• Integer circuit
• Interactive proof system
• Introduction to the Theory of Computation

K

• Klee–Minty cube
• Kolmogorov complexity

L

• L-notation
• Leaf language
• Lempel–Ziv complexity
• List decoding
• Log-rank conjecture
• Log-space computable function
• Log-space reduction
• Log-space transducer
• Logical depth
• Low (complexity)
• Low-complexity art

M

• Mahaney's theorem
• Many-one reduction
• Model of computation

N

• Natural proof
• Noisy intermediate-scale quantum era
• Non-constructive algorithm existence proofs
• Nondeterministic algorithm

P

• Parameterized complexity
• Pebble game
• Polynomial-time reduction
• Proof (truth)
• Proof complexity
• Proof of knowledge
• Proper complexity function
• Propositional proof system
• Pseudo-polynomial time
• Pseudo-polynomial transformation

Q

• Quantum capacity
• Quantum complexity theory
• Quantum computing
• Quantum supremacy
• Quasi-polynomial growth
• Quasi-polynomial time

R

• Randomness extractor
• Randomness merger
• Reduction (complexity)

S

• Semi-membership
• Engineering:Silq
• Smoothed analysis
• Space complexity
• Sparse language
• Strong NP-completeness
• Switching lemma
• Symmetric Turing machine

T

• Time complexity
• Tractable problem
• Transcomputational problem
• Transdichotomous model
• Truth-table reduction
• Turing reduction

U

• Unary language
• Union theorem
• Software:Unique games conjecture
• Universal hashing

W

• Weak NP-completeness

Y

• Yao's principle