Lukas' Notes

Polynomial Time Complexity

1 min read

complexity-theory

Backlinks

Lecture 1-2 (Basics)
October 11, 2024 (2nd Exam for SS 2024)
Approximation's Collapse to Exactness
Binary Encoding is Compact
Pseudo-Polynomial Dynamic Programming is about Compression
Subexponential Time Needs a Ruler
3-Satisfiability Decision Problem
Approximation Complexity Class
Clique Decision Problem
Cobham-Edmonds Thesis
Constant-factor Approximation Algorithm
Cook Reduction
Dominating Set Problem
Factor-δ Approximation Algorithm
Graham's List Scheduling Algorithm
Intractable Problem
Karp Reduction
Verification (Nondeterministic Turing Machine)
Many-one Reduction
NP-Optimisation Decision Problem
NP-Optimisation Problem
NP-hard Problem
P equals NP
P not equals NP
P vs NP Problem
Polynomial Complexity Class
Polynomial Decidable Binary Relation
Polynomial Time Reduction
Polynomial-time Algorithm
Polynomial-time Approximation Algorithm
Polynomial-time Approximation Scheme
Polynomially Related Encoding
Pseudo-Polynomial Time Complexity
Reduction
Star Sum Problem
Strong NP-Hard Decision Problem
Strong NP-Hardness Rules Out FPTAS
Time Complexity
Tractable Problem
Turing Reduction
Vertex Cover Problem
Weak NP-Hard Decision Problem
Winner Determination Problem (COMSOC)
Quantum Algorithms for Lattice Problems

Created with Quartz v4.5.2 © 2026

GitHub