计算复杂性理论50年：从P与NP问题到元复杂性

文章预览

导语 证明一个问题难以解决这件事究竟有多难？这是元复杂性理论学家一直追问的问题。经过数十年，探索的路径从P与NP问题转变到元复杂性问题，他们试图通过复杂性理论的视角观察复杂性理论本身。 研究领域： 计算复杂性，理论计算机科学，P与NP问题， 信息论，元复杂性，自指 Ángel Goñi-Moreno   | 作者 朱欣怡   | 译者 梁金   | 审校 文章题目：Complexity Theory’s 50-Year Journey to the Limits of Knowledge 文章链接：https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/ 目录 1. 起源 2. 障碍 3. 机遇 复杂性理论发展的100年历程。｜来源：Samuel Velasco/ Quanta Magazine 1. 起源 2007年秋季学期，Marco Carmosino 在读大二，正考虑从大学退学去设计电子游戏。开学第一周，他硬着头皮去参加马塞诸塞大学阿默斯特分校计算机科学专业必修的数学课。 ………………………………