#Computational-Complexity
3 posts in tag “Computational-Complexity”.
The PCP Theorem: Why Some Problems Are Hard Even to Approximate
2025-03-30Unpack one of theoretical computer science's crown jewels: the PCP theorem, which shows that for many NP-hard problems, even finding an approximate solution is intractable — and how probabilistically checkable proofs revolutionized our understanding of hardness.
Algorithmic Game Theory: Nash Equilibrium Computation, PPAD-Completeness, and the Computational Lens on Strategy
2019-11-23A rigorous look at algorithmic game theory—computing Nash equilibria, the PPAD complexity class, and how computational constraints reshape strategic reasoning.
NP-Completeness: The Cook-Levin Theorem, Polynomial Reductions, and the Hardest Problems in NP
2019-05-03A deep dive into the theory of NP-completeness—from Turing machines and the Cook-Levin theorem to the taxonomy of NP-complete problems and the P versus NP question.