The P versus NP problem - Efficient computation and the limits of human knowledge - AVI Wigderson

Speaker : Avi Wigderson ( IAS, Princeton ) Date and Time : 27 Dec 2009, 05:30 PM Venue : J. N. Tata Auditorium, IISc, Bangalore The P vs. NP problem is a central outstanding problem of computer science and mathematics. In this talk I will attempt to describe its technical, scientific and philosophical content, its status, and the implications of its two possible resolutions. Table of Contents (powered by https://videoken.com) 0:00:00 [Video] 0:03:58 Introduction 0:14:59 Efficient computation, Internet security, and the limits of human knowledge 0:15:49 Clay Math Institute Millennium Problems - $1M each 0:17:17 Scientific / Mathematical/ Intellectual Computational problems NP; Problems we 0:17:40 Plan: Computation is everywhere Algorithms: language of computationEfficient algorithms: 0:18:24 Computation 0:18:52 Computation is everywhere 0:19:28 Nature computes! can we simulate/predict? 0:20:55 Will the epidemic spread, or die out? 0:21:08 Computations in Mathematics 0:21:59 Seashells compute 0:22:08 How to describe computation? 0:22:28 Father of Computing 0:24:33 Algorithm 0:26:36 Limits of Knowledge I Unsolvable vs Solvable 0:29:33 How many steps to solve. 0:30:00 How long does it take you to solve. 0:34:21 Which predictions are hard to solve? Addition & Multiplication: Easy 0:34:49 The class P 0:35:54 Efficient algorithms - Drivers of invention & industry 0:36:49 Shortest path - Dijkstra 1959 0:39:34 Unsolvable vs Solvable 0:40:27 Search problems 0:43:09 The class NP - problems like -FIND: needle in a haystack 0:43:40 The class NP 0:45:21 P versus NP 0:46:51 What is in NP? 0:50:13 Universality NP 0:56:29 P - NP as a law of nature 1:00:38 What is efficient computation? 1:03:29 Q&A