Lukas' Notes
Search
Search
Dark mode
Light mode
Tag: complexity-theory
93 items with this tag.
2-SAT4 Satisfiability Decision Problem
complexity-theory
propositional-logic
3-Horn Satisfiability Decision Problem
complexity-theory
propositional-logic
3-SAT to 3-Horn SAT (Karp Reduction)
complexity-theory
reductions
propositional-logic
3-SAT to Dominating Set (Karp Reduction)
complexity-theory
graph-theory
reductions
exponential-time-hypothesis
3-SAT to Subset Sum (Karp Reduction)
complexity-theory
reductions
3-SAT to Vector Subset Sum (Karp Reduction)
complexity-theory
reductions
subset-sum
A Reduction Transfers Hardness, Not Weakness
complexity-theory
reductions
Algorithm Complexity
complexity-theory
Approximation Complexity Class
complexity-theory
Asymptotic Dominance
complexity-theory
Average-case Runtime
complexity-theory
Best-case Running Time
computation
complexity-theory
Best-case Runtime
complexity-theory
Big-O Notation
complexity-theory
Big-Omega Notation
complexity-theory
Big-Theta Notation
complexity-theory
C-complete Decision Problem
computation
complexity-theory
C-hard Decision Problem
computation
complexity-theory
Certificate (Complexity Theory)
complexity-theory
Chamberlin-Courant Winner Determination Decision Problem
comsoc
complexity-theory
Chamberlin-Courant Winner Determination Search Problem
comsoc
complexity-theory
Cobham-Edmonds Thesis
complexity-theory
Complement Complexity Class
complexity-theory
Complexity Class
complexity-theory
Complexity Class Membership
computation
complexity-theory
Complexity Theory
complexity-theory
Constant Time Complexity
complexity-theory
Counting Problem
complexity-theory
computation
Dichotomy Theorem (Constraint Satisfaction)
complexity-theory
constraint-satisfaction
Dominating Set to Integer Linear Programming (Karp Reduction)
complexity-theory
reductions
integer-programming
graph-theory
Exponential Complexity
complexity-theory
Exponential Time Hypothesis
complexity-theory
computation
EXPTIME Complexity Class
complexity-theory
Gadget
computation
complexity-theory
Independent Set to Chamberlin-Courant Winner Determination (Karp Reduction)
comsoc
complexity-theory
graph-theory
reductions
Independent Set to Clique (Karp Reduction)
complexity-theory
graph-theory
reductions
Independent Set to Proportional Winner Determination (Karp Reduction)
comsoc
complexity-theory
graph-theory
reductions
Independent Set to Vertex Cover (Karp Reduction)
complexity-theory
graph-theory
reductions
Integer Linear Programming
complexity-theory
Integer Linear Programming Decision Problem
complexity-theory
integer-programming
Ladner's Theorem
complexity-theory
Landau Symbols
complexity-theory
Linear Complexity
complexity-theory
Linear Programming
complexity-theory
Logarithmic Time Complexity
complexity-theory
Logspace Complexity Class
complexity-theory
Memory Requirement
complexity-theory
NEXPTIME Complexity Class
complexity-theory
Nondeterministic Logarithmic Space Complexity Class
complexity-theory
Nondeterministic Polynomial Complexity Class
complexity-theory
Nondeterministic Polynomial Problem
computation
complexity-theory
NP-complete Decision Problem
computation
complexity-theory
NP-hard Decision Problem
computation
complexity-theory
NP-intermediate Problem
complexity-theory
NP-Optimisation Decision Problem
complexity-theory
optimisation
NP-Optimisation Problem
complexity-theory
optimisation
P = NP Is Not About Stacking Paths
complexity-theory
nondeterministic-turing-machines
P = NP Starts with a Missing Arrow
complexity-theory
computational-complexity
P equals NP
complexity-theory
P not equals NP
complexity-theory
Poly Notation
complexity-theory
Polynomial Balanced Binary Relation
complexity-theory
Polynomial Complexity Class
complexity-theory
Polynomial Decidable Binary Relation
complexity-theory
Polynomial Running Time
computation
complexity-theory
Polynomial Space Complexity
complexity-theory
Polynomial Time Complexity
complexity-theory
Polynomial Time Reduction
complexity-theory
Polynomially Related Encoding
complexity-theory
Proportional Winner Determination Decision Problem
comsoc
complexity-theory
Proportional Winner Determination Search Problem
comsoc
complexity-theory
Pseudo-Polynomial Time Complexity
complexity-theory
PSPACE Complexity Class
complexity-theory
Quasipolynomial Running Time
computation
complexity-theory
Restriction (Decision Problem)
complexity-theory
Running Time
computation
complexity-theory
Runtime
complexity-theory
SAT to Independent Set (Karp Reduction)
complexity-theory
graph-theory
reductions
Small-O Notation
complexity-theory
Small-Omega Notation
complexity-theory
Space Complexity
complexity-theory
Strong NP-Hard Decision Problem
complexity-theory
np-hardness
Subset Sum Problem
complexity-theory
Subset Sum to Integer Linear Programming (Karp Reduction)
complexity-theory
reductions
The Exponent Is the Terrain
complexity-theory
asymptotic-analysis
Time Complexity
complexity-theory
Two-Bag Knapsack Decision Problem
complexity-theory
knapsack
Vector Subset Sum Decision Problem
complexity-theory
subset-sum
Vertex Cover to Dominating Set (Karp Reduction)
complexity-theory
graph-theory
reductions
Vertex Cover to Integer Linear Programming (Karp Reduction)
complexity-theory
graph-theory
reductions
Weak NP-Hard Decision Problem
complexity-theory
np-hardness
Worst-Case Complexity
complexity-theory
Worst-case Running Time
computation
complexity-theory
1
2
3
4
5
6
7
8
9
10
Page 1 of 10