公共目录

您目前的位置: 首页» 公共目录» 学术活动

学术报告:Limits on Computation and Complexity

首都师范大学学术报告 题      目:Limits on Computation and Complexity 主 讲 人:Phil Grant (Associate Professor) (Department of Computer Science, College of Science, Swansea University, UK) 时      间:2014年3月17日(周一)16:30 地      点:首师大北二区二层大会议室 主 办 单 位:首都师范大学信息工程学院 内 容 介 绍: Outline of Talk:1 The notion of computability. 2                                   Non computable functions. 3 Computational Complexity. 4 P vs NP   Computational Complexity: Bounded halting problem. Cook and Sat. Karp - produced list of 21 NP-complete problems. Cook & Karp received Turing Award (1982 and 1985) Example of a reduction of Sat to problem. One of Clay Millennium Problems - win $1,000,000!   Summary:    Have introduced the notion of computable function. Shown there are non-computable functions. Then added constraints such as time and space bounds. Tractable problems—in P. Difficult problems— in NP. NP complete problems. Unresolved P vs NP problem.