Skip to main content

Computational complexity

2014-10-17 — 2014-10-17

quality 2.8

Wherein the Interplay of Abstract Decision Problems and Physical Limitations Is Examined, and the Prospects of Simulating Entire Worlds via Computational Models and NP‑complete Barriers Are Considered.

complexity
compsci
pseudorandomness

Not my area, but I should note my favourite “wow, cool” readings somewhere.

1 References

Aaronson. 2005. “NP-Complete Problems and Physical Reality.” SIGACT News.
Arora, and Barak. 2009. Computational Complexity: A Modern Approach.
Moore, and Mertens. 2011. The Nature of Computation.
Opedal, Zengaffinen, Shirakami, et al. 2025. “Are Language Models Efficient Reasoners? A Perspective from Logic Programming.”
Roughgarden. 2018. “Complexity Theory, Game Theory, and Economics.” arXiv:1801.00734 [Cs, Econ].
Saari, and Xia. 1995. “Off to Infinity in Finite Time.” Notices of the AMS.
Viola. 2026. “Mathematics of the Impossible.”