Category:Computational complexity theory
![]() | Computing portal |
Here is a list of articles in the Computational complexity theory category of the Computing portal that unifies foundations of mathematics and computations using computers.
Subcategories
This category has the following 11 subcategories, out of 11 total.
A
C
D
N
P
Q
S
T
Pages in category "Computational complexity theory"
The following 111 pages are in this category, out of 111 total.
- 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)