Category:Computational complexity theory

A

• [+] Analysis of algorithms (24 P)

C

• [+] Circuit complexity (13 P)
• [+] Complexity classes (1 C, 85 P)
• [+] Computational hardness assumptions (15 P)

C cont.

• [+] Computational problems (9 C, 22 P)
• [+] Computational resources (5 P)

D

• [+] Descriptive complexity (8 P)

P

• [+] Probabilistic complexity theory (1 C, 15 P)

Q

• [+] Quantum complexity theory (9 P)

S

• [+] Structural complexity theory (1 C, 15 P)

*

• Computational complexity theory
• Complexity class

A

• Aanderaa–Karp–Rosenberg conjecture
• Accounting method
• Advice (complexity)
• AI-complete
• Almost complete
• Analysis of algorithms
• Approximation algorithm
• Asymptotic computational complexity
• Asymptotically optimal algorithm
• Averaging argument

B

• Best, worst and average case
• Blum's speedup theorem
• Boolean circuit

C

• Certificate (complexity)
• Circuit complexity
• Cobham's thesis
• Combinatorial optimization
• Communication complexity
• Complement (complexity)
• Complete (complexity)
• Complexity
• Complexity index
• The Complexity of Songs
• Compression theorem
• Computation tree
• Computational complexity of mathematical operations
• Computational resource
• Computational topology
• Computing the permanent

C cont.

• Constructible function
• Context of computational complexity
• Cook–Levin theorem

D

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

E

• Effective complexity

G

• Gadget (computer science)
• Gap theorem
• Generalized game

H

• Hardness of approximation

I

• Information-based complexity
• Interactive proof system
• Interval-valued computation
• Introduction to the Theory of Computation

K

• Karp–Lipton theorem
• Kernelization
• Kolmogorov structure function

L

• L-notation
• L-reduction
• Leaf language
• Linear speedup theorem
• Linearithmic function
• List-decoding
• Log-space reduction
• Logical depth
• Low (complexity)

M

• Many-one reduction
• Minimum weight triangulation

M cont.

• Molecular models of DNA
• Multilinear polynomial

N

• Natural proof
• Negational normal form
• Nondeterministic algorithm

P

• PCP theorem
• PTAS reduction
• Parameterized complexity
• Pebble game
• Polynomial-time reduction
• Proof complexity
• Proper complexity function
• Pseudorandom generator theorem

Q

• Quantum computer
• Quantum complexity theory

R

• Randomness extractor
• Reduction (complexity)

S

• Schaefer's dichotomy theorem
• Self-dissimilarity
• Smoothed analysis
• Sparse language
• Speedup theorem
• Sublinear time algorithm
• Symmetric Turing machine

T

• Truth table reduction
• Turing reduction

U

• Unary language
• Uniformity (complexity)
• Unique games conjecture
• Universal hashing

Y

• Yao's principle