Lukas' Notes
Search
Search
Dark mode
Light mode
Polynomial Time Complexity
May 01, 2026
1 min read
complexity-theory
Graph View
Backlinks
Approximation's Collapse to Exactness
Binary Encoding is Compact
Pseudo-Polynomial Dynamic Programming is about Compression
Clique Problem
Cobham-Edmonds Thesis
Cook Reduction
Dominating Set Problem
Factor-Delta Approximation Algorithm
Intractable Problem
Karp Reduction
Many-One Reduction
NP-Optimisation Problem
NP-hard Problem
Nondeterministic Polynomial Problem
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
Time Complexity
Tractable Problem
Turing Reduction
Vertex Cover Problem
Weak NP-Hard Problem
Quantum Algorithms for Lattice Problems