2021年10月10日上午十點，國家特聘專家，烏鎮智庫理事長，圖靈算力研究院院長張曉東教授應伟德国际BETVlCTOR邀請，在伟德国际BETVlCTOR中心校區計算機樓A521報告廳作了題為“計算複雜性50年：王浩與計算理論”的專題報告，這是本科生綜合素質提升計劃系列報告的第五場，報告由伟德国际BETVlCTOR副院長張永剛教授主持，計算機學院、軟件學院共30餘名本科生參加了此次報告會。
張曉東教授（筆名，尼克）。國家特聘專家，烏鎮智庫理事長，圖靈算力研究院院長。畢業于天津大學，中科院和美國麻省大學。早年在哈佛從事生物信息學研究，後在HP負責互聯網支付項目。曾連環創業，并擔任VC合夥人和上市公司獨立董事，所著《人工智能簡史》獲吳文俊獎和中華優秀出版物獎。
從1971年Cook文章發表日開始算，到2021年計算複雜性理論正好50歲。今年又恰逢Cook的導師王浩誕辰100年，本次報告中張曉東教授為大家回溯計算複雜性的起源，并力圖梳理王浩和這門學科的關系。本次報告主要包括三方面内容：
首先，是梳理計算複雜性的源頭。早在20世紀30年代就有數學家提出“計算複雜性”的概念，到20世紀50年代，納什提出了多項式複雜性和指數複雜性的區别，他推測指數複雜性對加密算法是有用的。Cobham在1964年的科學哲學大會上發表過計算複雜性相關的文章。但那個時期的計算複雜性并未得到充分的重視，計算機科學作為一門獨立的學科剛剛開始，數學系的主流還沒把計算理論當回事。
Cook對計算複雜性的貢獻是他在1971年證明了命題邏輯的可滿足性問題（SAT）是NP完全的。用命題邏輯來描述非确定圖靈機多項式時間運行的所有可能狀态，他的論文題目和定理證明相關。Cook的工作影響了很多人，包括圖靈獎獲得者Leslie Valiant。數學家斯梅爾對他工作的評價是：計算機科學給數學的禮物。
再到王浩：Cook用到的方法受到王浩啟發，cook自己也承認他對NP完全問題的結論與王浩的AEA非常類似，他的文章裡也引用了王浩的一些邏輯演算。張教授認為，在可計算性理論和計算複雜性理論之間，王浩起了承上啟下的作用。他被忽視，有外在的原因：圖靈和Cook影響過于深廣；另一方面，也有内在的原因，王浩晚年轉向哲學，對計算理論興趣不大。但是王浩對計算複雜性的貢獻不能被淹沒在曆史的河流中，年輕的學子應該知道他在這個領域中做出的貢獻。
張教授的報告風趣幽默、内容紮實，讓在場聽衆了解了計算複雜性這一學科的發展曆程和對這門學科做出過貢獻的偉大科學家們，一門學科的發展是無數人共同努力的結果，無論成就大小，所有做過貢獻的人都值得被銘記。伟德国际BETVlCTOR副院長張永剛教授代表伟德国际BETVlCTOR計算機學科對張教授撥冗前來進行本科生綜合素質提升指導表示了感謝。本次本科生綜合素質提升系列報告是伟德国际BETVlCTOR本科生培養和素質提升的重要組成部分，後續将繼續舉辦其他本科生綜合素質提升計劃系列報告。
伟德国际BETVlCTOR
