学术报告:Limits on Computation and Complexity
来源: 发布日期:2014-03-13
首都师范大学学术报告
题 目: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.