Category:Computational complexity theory

A

• [+] Analysis of algorithms (0)

C

• [+] Circuit complexity (0)

C cont.

• [+] Computational hardness assumptions (0)
• [+] Computational problems (7)
• [+] Computational resources (0)

D

• [+] Descriptive complexity (0)

P

• [+] Probabilistic complexity theory (1)

S

• [+] Structural complexity theory (1)

• DNA Dynamics

*

• Computational complexity theory
• Quantum computer
• Complexity class
• Molecular models of DNA
• User:Bci2/Books/Wk2Book
• User:Bci2/Books/Wk3vol1
• User:Bci2/Books/Wk4

2

• 2-satisfiability

3

• 3SUM

A

• Accounting method
• Advice (complexity)
• AI-complete
• Almost complete
• Analysis of algorithms
• Approximation algorithm
• Arithmetic circuit complexity
• Asymptotic computational complexity
• Asymptotically optimal algorithm

B

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

C

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

C cont.

• Computing the permanent
• Constant time
• Constructible function
• Context of computational complexity
• Cook–Levin theorem

D

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

E

• Element uniqueness problem
• Exponential time

G

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

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
• LOGCFL
• Leaf language
• Linear search problem
• Linear speedup theorem
• Linear time
• Linearithmic function
• List-decoding
• Log-space reduction
• Low (complexity)

M

• MAX-3LIN-EQN
• MAX-3SAT(13)
• MAXEkSAT
• Many-one reduction
• Minimum weight triangulation

M cont.

• Multilinear polynomial

N

• Natural proof
• Negational normal form
• Nondeterministic algorithm

O

• O-speedup
• Optimization problem

P

• P-nonuniform
• PCP theorem
• PTAS reduction
• Parameterized complexity
• Pebble game
• Polynomial space
• Polynomial time
• Polynomial-time reduction
• Probabilistic complexity
• Problem size
• Proof complexity
• Proper complexity function
• Pseudo-polynomial time
• Pseudorandom generator theorem

R

• Randomness extractor
• Reduction (complexity)

S

• (SAT, ε-UNSAT)
• Schaefer's dichotomy theorem
• Smoothed analysis
• Smoothed complexity
• Speedup theorem
• St-connectivity
• Sub-exponential time
• Sublinear time algorithm
• Sum of radicals

T

• True quantified Boolean formula
• Truth table reduction
• Turing reduction

U

• Unique games conjecture
• Universal hashing
• Unknotting problem

Y

• Yao's principle