Category:Computational complexity theory

A

• ► Analysis of algorithms‎ (1 C, 32 P)

C

• ► Circuit complexity‎ (17 P)
• ► Complexity classes‎ (1 C, 86 P)
• ► Computational hardness assumptions‎ (17 P)
• ► Computational problems‎ (10 C, 24 P)

C cont.

• ► Computational resources‎ (8 P)

D

• ► Descriptive complexity‎ (9 P)

N

• ► NP-complete problems‎ (7 C, 75 P)

P

• ► Parameterized complexity‎ (1 C, 4 P)
• ► Probabilistic complexity theory‎ (1 C, 20 P)

Q

• ► Quantum complexity theory‎ (10 P)

S

• ► Strongly NP-complete problems‎ (1 C, 4 P)
• ► Structural complexity theory‎ (1 C, 15 P)

• Computational complexity theory

*

• Complexity class
• Configuration graph
• Padding argument

A

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

B

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

C

• Certificate (complexity)
• Circuit complexity
• Circuits over sets of natural numbers
• Cobham's thesis
• Combinatorial optimization
• Communication complexity
• Complement (complexity)
• Complete (complexity)
• Complexity index
• The Complexity of Songs
• Compression theorem
• Computation tree
• Computational complexity of mathematical operations
• Computational resource
• Computational topology
• Computing the permanent
• Constructible function
• Context of computational complexity
• Cook–Levin theorem

D

• Decision tree model
• Descriptive complexity theory

D cont.

• Dynamic problem (algorithms)

E

• User:ECCclass/list-decoding
• Effective complexity
• Electronic Colloquium on Computational Complexity
• Existential theory of the reals

G

• Gadget (computer science)
• Gap theorem
• Generalized game
• Generic-case complexity

H

• Hardness of approximation
• HO (complexity)

I

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

K

• Karp–Lipton theorem
• Klee–Minty cube

L

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

M

• Many-one reduction

N

• Natural proof
• Nondeterministic algorithm

P

• Parameterized complexity
• PCP theorem
• Pebble game
• Polynomial-time reduction
• Proof (truth)

P cont.

• Proof complexity
• Proper complexity function
• Propositional proof system
• Pseudo-polynomial time
• Pseudorandom generator theorem
• PTAS reduction

Q

• Quantum capacity
• Quantum complexity theory
• Quantum computer

R

• Randomness extractor
• Reduction (complexity)

S

• Savitch's theorem
• Schaefer's dichotomy theorem
• Semi-membership
• Smoothed analysis
• SO (complexity)
• Sparse language
• Speedup theorem
• Strongly NP-complete
• Switching lemma
• Symmetric Turing machine

T

• User:Thore Husfeldt/sandbox
• Time complexity
• Transcomputational problem
• Transdichotomous model
• Truth-table reduction
• Turing reduction

U

• Unary language
• Unique games conjecture
• Universal hashing

W

• Weakly NP-complete

Y

• Yao's principle