Unlocking the Mystery of P vs. NP: The Limits of Computation 🧠

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