Foundational Papers in Complexity Science pp. 1207–1236
DOI: 10.37911/9781947864535.40
Gardens of Forking Paths: Exponential Hardness and Exhaustive Search
Author: Cristopher Moore, Santa Fe Institute
Excerpt
Which problems are easy, and which are hard? And what is it about their structure that makes them so?
There are many ways to think about this question, but one of the most mathematically well-developed is computational complexity theory. Here we regard a problem as easy if there is an algorithm that solves it efficiently: that quickly finds a solution or quickly determines whether a solution exists. If there is no such algorithm—if our only recourse is to methodically search a vast landscape of possible solutions—then the problem is hard.
Many real-world problems certainly seem hard. Can we arrange a supply chain to produce a product by a certain date? How can we design a power grid that stores and delivers energy at the times and to the places it is needed? Which groups of people should we vaccinate or test most urgently to halt the spread of an epidemic? Problems like these are hard partly because there are many possible strategies for solving them and partly because of our uncertainty about the world. Our solutions may founder because we don’t understand how a disease spreads, or how electricity demand will change, or whether vital materials and techniques will be available. Even worse, we may not even agree on our values—the “objective function” or “fitness function” that we are trying to optimize.
Bibliography
Babai, L. 2015. “Graph Isomorphism in Polynomial Time.” arXiv 1512.03547 [cs.DS]. https://doi.org/10.48550/arXiv.1512.03547.
Cook, S. A. 1971. “The Complexity of Theorem-Proving Procedures.” In STOC ’71: Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151–158. New York, NY: Association for Computing Machinery.
Khachiyan, L. G. 1979. “A Polynomial Algorithm in Linear Programming.” Translated in Soviet Mathematics Doklady 20, 191–194, 1979, Doklady Akademii Nauk SSSR 244:1093–1096.
Nash, J., and National Security Agency. 1955 [2012]. Correspondences Regarding Cryptography between John Nash and the NSA. Declassified by the NSA. https://www.nsa.gov/Portals/70/documents/news-features/press-room/press-releases/2012/nash-exhibit/nash_letters1.pdf.