Category:Computational complexity theory

A

• ► Analysis of algorithms‎ (3 C, 45 P)

C

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

D

• ► Descriptive complexity‎ (10 P)

N

• ► NP-complete problems‎ (85 P)

P

• ► Parameterized complexity‎ (1 C, 6 P)

Q

• ► Quantum complexity theory‎ (15 P)
• ► Quantum computing‎ (2 C, 57 P)

S

• ► Structural complexity theory‎ (1 C, 17 P)

T

• ► Theorems in computational complexity theory‎ (20 P)

• Computational complexity theory (computing)

*

• Complexity class (computing)
• Padding argument (computing)

A

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

B

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

C

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

D

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

E

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

F

• Folded Reed–Solomon code (computing)

G

• Gadget (computer science) (computing)
• Gap-Hamming problem (computing)
• Generalized game (computing)
• Generic-case complexity (computing)
• Geometric complexity theory (computing)

H

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

I

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

K

• Klee–Minty cube (computing)

L

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

M

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

N

• Natural proof (computing)
• Non-constructive algorithm existence proofs (computing)
• Nondeterministic algorithm (computing)

P

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

Q

• Quantum capacity (computing)
• Quantum complexity theory (computing)
• Quantum computing (engineering)
• Quantum supremacy (computing)

R

• Randomness extractor (computing)
• Randomness merger (computing)
• Reduction (complexity) (computing)

S

• Semi-membership (computing)
• Smoothed analysis (computing)
• Space complexity (computing)
• Sparse language (computing)
• Strong NP-completeness (computing)
• Switching lemma (computing)
• Symmetric Turing machine (computing)

T

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

U

• Unary language (computing)
• Unique games conjecture (computing)
• Universal hashing (computing)

W

• Weak NP-completeness (computing)

Y

• Yao's principle (computing)