Category:Computational complexity theory

A

• ► Analysis of algorithms‎ (22 P)

C

• ► Circuit complexity‎ (12 P)
• ► Complexity classes‎ (71 P)
• ► Computational problems‎ (7 C, 18 P)
• ► Computational resources‎ (9 P)

D

• ► Descriptive complexity‎ (7 P)

N

• ► NP-complete problems‎ (2 C, 52 P)

Q

• ► Quantum complexity theory‎ (8 P)

• Computational complexity theory

*

• Complexity class

A

• Advice (complexity)
• Analysis of algorithms
• Approximation algorithm
• Averaging argument

B

• Best, worst and average case
• Boolean circuit

C

• Circuit complexity
• Cobham's thesis
• Combinatorial optimization
• Combinatorial search
• Communication complexity
• Complement (complexity)
• Complete (complexity)
• The Complexity of Songs
• Compression theorem
• Computation tree
• Computational complexity of mathematical operations
• Computational resource
• Computational topology
• Constructible function
• Context of computational complexity

D

• Descriptive complexity theory
• Dynamic problem (algorithms)

E

• Effective complexity
• Electronic Colloquium on Computational Complexity

F

• Folded Reed–Solomon code

G

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

I

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

L

• L-notation
• L-reduction
• Log-space reduction
• Logical depth

M

• Many-one reduction

N

• Natural proof
• Nondeterministic algorithm

P

• Parameterized complexity
• Polynomial-time reduction
• Proof complexity
• Proper complexity function
• Pseudo-polynomial time
• PTAS reduction

Q

• Quantum capacity
• Quantum complexity theory
• Quantum computing

R

• Randomness extractor
• Reduction (complexity)

S

• Semi-membership
• Smoothed analysis
• Strong NP-completeness
• Symmetric Turing machine

T

• Time complexity
• Transdichotomous model
• Truth-table reduction
• Turing reduction

U

• Unique games conjecture
• Universal hashing

W

• Weak NP-completeness

Y

• Yao's principle