Mathematics and Computation: The Landscape of P vs. NP

Name: Mathematics and Computation: The Landscape of P vs. NP
Uploaded: 2025-10-24T14:24:31.000Z
Duration: 1 h 2 min 49 s
Channel: Avi Wigderson
Description: Surveys computational hardness, pseudorandomness, interactive proofs, and why resolving P vs. NP sits at the heart of mathematical knowledge itself.

Avi Wigderson

1:04

2:07

2:41

2:51

2:08

0:57

3:02

2:42

1:11

2:25

2:55

4:00

0:40

3:49

2:11

1:00

3:00

1:00

1:40

2:20

2:50

1:20

1:45

1:35

2:20

2:10

1:45

1:15

1:00

1:49

Mathematics and Computation: The Landscape of P vs. NP

Avi Wigderson Institute for Advanced Study at Clay Mathematics Institute

1:02:49·2025·undergraduate·Public Lecture

Surveys computational hardness, pseudorandomness, interactive proofs, and why resolving P vs. NP sits at the heart of mathematical knowledge itself.

Surveys the P versus NP problem, tracing its historical roots from Hilbert's dream and Turing's formalization of computation to modern structural complexity. Explores the landscape of NP-completeness, constraint satisfaction dichotomies, PCP theorem, hardness-versus-randomness paradigms, interactive proofs, and barriers to proving circuit lower bounds.

Theory & Algos Computational Complexity Cryptography P vs NP & NP-Completeness Zero-Knowledge & Interactive Proofs Circuit & Space Complexity

Lecture Guide

1P versus NP addresses the fundamental limits of human knowledge, distinguishing problems solvable efficiently from those where solutions can only be verified quickly.
2NP-complete problems share a universal property where an efficient algorithm for one would solve all problems in NP.
3Constraint satisfaction and PCP theorems establish sharp thresholds between easy and hard approximation problems.
4Computational hardness can be traded for pseudorandomness, suggesting that randomness is not strictly necessary for efficient algorithms.

Proofs, Examples & Demos

Assumed Background

Optimization Taught @ 1:04 →

About the lecturer

Speaker directory →

Avi Wigderson

Website

Turing & Abel Prize Laureate, Herbert H. Maass Professor

Herbert H. Maass Professor at the Institute for Advanced Study and the only scholar to receive both the Abel Prize and the ACM Turing Award.

1 lecture in archiveView profile

Discussion

Share a seminar note, question, or timestamped reference (e.g. 14:20)...Sign in

Books by the lecturer

Mathematics and Computation

Avi Wigderson

Princeton University Press · 2019 · 1st Edition

Turing and Abel Prize Laureate Avi Wigderson's sweeping monograph on P vs. NP, randomness, zero-knowledge proofs, and computational complexity.

Related lectures

5