回首頁

回第27期

計算複雜性理論的50 年知識極限之旅
證明問題難解有多困難？像這樣的問題元複雜性理論家一直問了幾十年。一連串近期的結果開始給出答案。

本文預覽

作　　者　布魯貝克（Ben Brubaker）

作者簡介　布魯貝克是《Quanta》雜誌資訊科學領域的特約撰稿人。他先前曾以自由記者報導物理學，文章也出現在《科學人》（Scientific American）、《今日物理》（Physics Today）等雜誌上。他擁有耶魯大學物理學博士學位，並在科羅拉多大學博爾德分校進行博士後研究。

譯　　者　林武雄

譯者簡介　林武雄是國立陽明交通大學應用數學系助理教授。

本文出處    Quanta Magazine Aug 17, 2023。

延伸閱讀　

• https://www.youtube.com/watch?v=pQsdygaYcE4&t=7s  這是Quanta Magazine 配合本文的YouTube 影片《資訊科學的最大難題——P 與NP 問題》，讀者可配合本文觀賞。
• 福特諾，The Golden Ticket: P, NP, and the Search for the Impossible, Princeton University Press, 2013。這本書有簡體中文翻譯《可能與不可能的邊界：P/NP 問題趣史》，楊凡譯，人民郵電出版社，2014 年。