Avi Wigderson Casts P vs. NP as Boundary of Human Knowledge

Ryan Peterman

An algorithmic proof that P equals NP would ensure any problem with a recognizable solution can be solved efficiently, unlocking everything humanity seeks to know.

AI-assisted summary of Turing Award & Abel Prize Winner Explains P vs. NP | Avi Wigderson — original source. Check the original for full context.

Source published: 2026-07-31

Key ideas

Avi Wigderson frames P versus NP as a foundational question about human knowledge: whether humanity can solve all the problems it wants to solve. (0:00)
The complexity class NP represents the universe of problems humanity cares about solving, characterized by candidate solutions that can be easily verified once found. (1:45)
The complexity class P comprises problems solvable within a lifetime using efficient algorithms on modern computers. (1:45)
If P equals NP, any problem whose solution can be recognized—such as discovering a cure for cancer or finding mathematical proofs—could be solved efficiently. (1:45)

Detailed notes

## Background Published on YouTube by Ryan Peterman on July 31, 2026, this video is an excerpt from an extended interview with Avi Wigderson, the only person to receive both the Turing Award and the Abel Prize. According to the page description, the clip focuses on Wigderson explaining the fundamentals of his field of theoretical computer science.

## TL;DR In this discussion, Avi Wigderson reframes the famous P versus NP problem from an abstract mathematical puzzle into a fundamental question about the limits of human knowledge. He explains that P represents the subset of challenges humanity can solve efficiently using algorithms, such as finding shortest paths in navigation software, while NP encompasses all problems whose proposed solutions can be easily verified once found. Because fields ranging from mathematics and empirical science to engineering and detective work only search for answers they can recognize and verify, NP encapsulates essentially everything humanity desires to solve. Consequently, if P equals NP, humanity possesses the theoretical capacity to efficiently discover solutions to any verifiable problem, from proving complex theorems to curing cancer.

## Atmosphere & style The conversation carries an intellectually luminous and reflective tone, shedding dry formalisms in favor of lucid, accessible philosophy. Wigderson speaks with warm authority and intuitive clarity, transforming intimidating computational complexity into relatable human pursuits like crime solving and bridge design. Listening feels like sitting in on an intimate masterclass where deep mathematical theory naturally converges with existential wonder about what minds can know.

## Bulletin - [00:00](https://www.youtube.com/watch?v=SHT3himqWHo&t=0s) Avi Wigderson frames P versus NP as a foundational question about human knowledge: whether humanity can solve all the problems it wants to solve. - [01:45](https://www.youtube.com/watch?v=SHT3himqWHo&t=105s) The complexity class NP represents the universe of problems humanity cares about solving, characterized by candidate solutions that can be easily verified once found. - [01:45](https://www.youtube.com/watch?v=SHT3himqWHo&t=105s) The complexity class P comprises problems solvable within a lifetime using efficient algorithms on modern computers. - [01:45](https://www.youtube.com/watch?v=SHT3himqWHo&t=105s) If P equals NP, any problem whose solution can be recognized—such as discovering a cure for cancer or finding mathematical proofs—could be solved efficiently.

## Key takeaways - [00:00](https://www.youtube.com/watch?v=SHT3himqWHo&t=0s) The P versus NP problem fundamentally investigates the limits of human knowledge and theoretical computational capability. - [00:00](https://www.youtube.com/watch?v=SHT3himqWHo&t=0s) Theoretical computer science categorizes human challenges into problems we desire to solve versus problems we have the capacity to solve. - [00:00](https://www.youtube.com/watch?v=SHT3himqWHo&t=0s) The collection of challenges humanity wants to understand and solve corresponds conceptually to the complexity class NP. - [00:00](https://www.youtube.com/watch?v=SHT3himqWHo&t=0s) The subset of problems humanity can solve efficiently in principle using algorithms corresponds to the class P. - [01:45](https://www.youtube.com/watch?v=SHT3himqWHo&t=105s) Class P captures problems that can be realistically resolved within our lifetime, exemplified by shortest-path routing in navigation apps. - [01:45](https://www.youtube.com/watch?v=SHT3himqWHo&t=105s) Class NP formally consists of problems where a proposed solution can be easily checked for correctness, regardless of how hard it is to find. - [01:45](https://www.youtube.com/watch?v=SHT3himqWHo&t=105s) Humanity naturally focuses on NP problems because people rarely pursue objectives without the ability to recognize a correct outcome. - [01:45](https://www.youtube.com/watch?v=SHT3himqWHo&t=105s) In mathematics, theorem proofs take years to discover but can be verified by the community once written down. - [01:45](https://www.youtube.com/watch?v=SHT3himqWHo&t=105s) In empirical science, candidate theories explaining observed phenomena can be checked for consistency against experimental data. - [01:45](https://www.youtube.com/watch?v=SHT3himqWHo&t=105s) In engineering, designs for smartphones or bridges can be readily inspected against physical and budgetary constraints. - [01:45](https://www.youtube.com/watch?v=SHT3himqWHo&t=105s) If P equals NP, the capacity to verify a solution guarantees an efficient method to find it, allowing humanity to solve challenges like curing cancer.

## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=SHT3himqWHo&t=0s) P vs. NP as the Limits of Human Knowledge

Ryan Peterman opens the discussion by referencing a point Avi Wigderson made in a previous lecture: that the famous $P$ versus $NP$ problem is fundamentally about the limits of human knowledge. Peterman asks Wigderson to unpack what $P$ versus $NP$ actually is and how it connects to what humans can know. Wigderson answers at a high level, explaining that human life is filled with a vast array of challenges—mathematical, scientific, medical, personal, and intellectual—and that computer science is fundamentally in the business of solving problems using computers.

To make sense of these challenges, theoretical computer science attempts to categorize them. On one side are all the problems humanity wants to understand and solve. On the other side are the problems humanity actually has the capacity to solve. In Wigderson's formulation, the collection of problems we care about solving corresponds to the mathematical class $NP$, while the subset of problems we can solve—not merely today, but in principle using efficient algorithms—corresponds to $P$. Framing the problem this way turns an abstract complexity-theory question into a profound philosophical inquiry. As Avi Wigderson summarizes: “So, the question of P versus NP is whether we can solve all the problems we want to solve, whether we can know everything we want to know.”

```mermaid flowchart TD accTitle: Conceptual View of P versus NP accDescr: Diagram showing how NP represents problems humanity wants to solve while P represents problems humanity can efficiently solve. subgraph NPClass ["NP: Problems We Want to Solve"] direction TB V["Solutions are easily verified once found"] subgraph PClass ["P: Problems We Can Solve"] S["Solutions can be found efficiently"] end end NPClass -->|"If P = NP"| FullKnowledge["Every verifiable problem can be solved efficiently"] ```

[01:45](https://www.youtube.com/watch?v=SHT3himqWHo&t=105s) Verifiable Solutions across Mathematics, Science, and Engineering

Wigderson moves on to justify why these formal mathematical definitions map directly onto human intuition. The class $P$ represents problems that can be solved within our lifetime using efficient algorithms on the computers we build. A tangible, everyday example is a navigation app on a smartphone: an engineer or computer scientist developed an efficient algorithm capable of computing the shortest path between any two locations on any road map.

```mermaid flowchart LR accTitle: Verification in Human Endeavors accDescr: Examples of four human endeavors where proposed solutions are verified against criteria. subgraph Endeavors ["Endeavors with Verifiable Solutions"] direction TB M["Math: Theorem proofs"] --> MV["Check peer-reviewed proof"] S["Science: Theories for data"] --> SV["Check consistency with observations"] E["Engineering: Bridge or phone design"] --> EV["Check physical and budget constraints"] D["Detective work: Crime solving"] --> DV["Check evidence and narrative"] end ```

By contrast, $NP$ is formally defined as the class of problems where—regardless of whether finding an answer is easy or hard—a candidate solution can be easily checked for correctness once presented. Wigderson argues that virtually every serious human pursuit falls into this category, because humans do not search for things they cannot recognize. As Avi Wigderson explains: “I mean, why would you ever start on looking for something if you would never recognize it as what you looked for?” He illustrates this across several distinct disciplines: - In mathematics, researchers spend years searching for proofs of theorems; once a proof is written in a paper, the mathematical community can verify its correctness. - In empirical science, researchers seek theories to explain observations about planetary motion or bacteria; once a theory is proposed, peer review checks whether it is consistent with the data. - In engineering, professionals design physical artifacts like bridges or smartphones subject to budgetary and physical constraints; clients and inspectors can readily inspect the finished design to ensure no constraints were violated. - In detective work, investigators gather evidence to solve a crime, producing a case that can be audited and evaluated.

Because the property of being able to easily recognize a correct answer unites all these endeavors, $NP$ encompasses everything humans honestly wish to solve. If $P$ were to equal $NP$, the mere ability to recognize a valid solution would guarantee the existence of an efficient way to discover it. Under that scenario, humanity could systematically uncover solutions to its greatest challenges, such as finding a cure for cancer. As Avi Wigderson concludes: “That means that we can know everything we ever want to know. It's a fundamental question about human knowledge.”

## Notable quotes > [00:00](https://www.youtube.com/watch?v=SHT3himqWHo&t=0s) So, the question of P versus NP is whether we can solve all the problems we want to solve, whether we can know everything we want to know. — Avi Wigderson

## Mentioned Avi Wigderson, Ryan Peterman, Turing Award, Abel Prize

## Video description Avi Wigderson is the only person in history to have won both a Turing Award (computer science) and Abel Prize (math). This is a clip from a longer interview I did with him all about his field.

Where to watch: • YouTube - https://youtu.be/5GUcvSAJcJw • Spotify - https://open.spotify.com/episode/4JZrdA7ciMKLSarhx7m9Lt?si=EXZof0ERRgS3_wsRmjYEzg • Apple Podcasts - https://podcasts.apple.com/us/podcast/the-peterman-pod/id1777363835 • Transcript - https://www.developing.dev/p/turing-award-winner-p-vs-np-zero

[Source](https://www.youtube.com/watch?v=SHT3himqWHo)

中文简报

威格森：P等于NP意味着人类可知晓其所探求的一切由于人类的几乎所有探索都需要识别有效解决方案，证明P等于NP将在数学上保证科学、数学和医学领域中每个可验证的问题都能被高效解决。阿维·威格森（Avi Wigderson）将著名的P与NP问题阐述为对人类认知边界的深刻哲学探索，而非单纯的技术难题。他将NP定义为人类渴望解决的广泛挑战合集——涵盖数学、科学、工程和侦查工作——其中任何候选解决方案都可以被轻易检验和验证。相比之下，P则包含了我们能够利用高效算法实际解决的问题子集，例如现代导航应用中的最短路径规划。如果P等于NP，那么识别正确答案的能力将从本质上确保高效找到答案的能力，这意味着人类能够系统性地攻克其最深奥的谜题，从治愈疾病到解决一切智力挑战。阿维·威格森从根本上将P对NP问题构建为一个关于人类认知极限的问题：我们是否能够解决我们想要解决的每个问题，并知晓我们希望知晓的一切。 (0:00) 计算复杂性类P代表可行的计算——即原则上可以在人类寿命内利用高效算法解决的问题，现代导航应用中的最短路径规划就是典型代表。 (1:55) NP类包含了其解一旦被找到便可轻易验证的问题，这一关键标准与科学、数学、工程和侦查工作中人类几乎所有的严肃探索相吻合。 (2:32) 如果P等于NP，那么识别正确解决方案的能力将在数学上保证高效找到该解的能力，从而使人类有能力解决诸如攻克癌症或解开任何科学谜团等挑战。 (4:50)

Reading summary

Avi Wigderson frames the computational complexity question of P versus NP as a fundamental inquiry into the limits of human knowledge, asking whether humanity can efficiently solve every challenge whose solution it can recognize. Mapping Algorithmic Classes to Human Capabilities (0:00) According to Avi Wigderson, theoretical computer science categorizes intellectual challenges by distinguishing the problems humanity wants to understand from those it actually has the capacity to solve. In this conceptual model, the mathematical class P corresponds to the subset of problems solvable within a lifetime using efficient algorithms on computers, such as navigation applications that rapidly compute the shortest path between two geographic points. Verifiable Discovery Across Intellectual Disciplines (1:45) Wigderson argues that the mathematical class NP captures virtually every serious human pursuit because people rarely search for solutions they cannot recognize. This structure applies across multiple fields: mathematicians spend years searching for proofs that the community can subsequently verify, empirical scientists propose theories that peer reviewers check against observational data, engineers produce designs that inspectors test against physical and budgetary constraints, and detectives assemble evidence that can be audited to solve crimes. Because the ability to verify a solution unites these disciplines, Wigderson notes that if P were to equal NP, the ability to recognize a correct answer would guarantee an efficient method to find it. In that scenario, humanity could systematically resolve its most complex challenges, including uncovering a cure for cancer, thereby demonstrating that we can know everything we want to know. Wigderson presents the resolution of P versus NP not merely as a technical puzzle in theoretical computer science, but as an ultimate determination of whether human problem-solving capacity is fundamentally limited or capable of answering every verifiable question.

精炼阅读摘要

图灵奖与阿贝尔奖得主 Avi Wigderson 指出，计算复杂性理论中的 P 与 NP 问题本质上探讨的是人类认知的终极边界，即人类是否能够在原则上解决所有渴望解决的问题。人类认知边界的数学映射 (0:00) 在与 Ryan Peterman 的对话中，Avi Wigderson 将人类在数学、科学、医学及个人生活层面面临的全部挑战置于理论计算机科学的框架中审视。他提出，计算机科学的核心目标是利用计算机解决实际问题，而理论研究则致力于对这些挑战进行分类。Wigderson 将人类渴望理解与解决的问题集合对应为复杂度类 NP，而将人类在原则上能够借助高效算法实际解决的问题集合对应为复杂度类 P。因此，P 是否等于 NP 这一抽象数学命题，直接对应着一个深刻的哲学命题：人类是否能够知道所有想知道的事情、攻克所有想解决的难题。 P类问题与高效算法的现实应用 (1:45) Wigderson 阐述了数学形式化定义与现实直觉的关联，指出复杂度类 P 代表那些在人类有生之年内、能够依托现有计算设备通过高效算法求解的问题。他以智能手机中的导航应用程序为例：工程师或计算机科学家开发出了能够在任意路线图上快速计算两点间最短路径的高效算法，使得普通用户可以即时获取出行方案，这体现了 P 类问题在技术与现实层面的可行性与确定性。 NP类问题覆盖人类探索的普遍特征 (1:45) 与 P 相比，NP 在形式上被定义为所有解法易于验证的问题集合，即无论寻找答案的过程多么艰难，一旦候选解答被提出，人们就能轻易核验其正确性。Wigderson 强调，人类几乎所有严肃的事业都落在 NP 的范畴内，因为人们通常不会去寻找自己完全无法辨识的事物。这一特征广泛存在于各个学科：数学家可能耗费数年证明定理，但同行能对论文进行有效验证；经验科学家提出理论解释行星或细菌数据，同行评审可核对其是否与观测一致；工程师设计桥梁或手机时必须满足物理和预算限制，监管者能审查设计是否合规；侦探破案后形成的证据链条同样可以被独立核实。 P与NP等价性的终极科学影响 (1:45) 基于 NP 涵盖了能够验证正确答案的全部人类诉求，Wigderson 进一步推论：若 P 最终被证明等于 NP，则意味着只要人类具备识别正确解的能力，就必然存在一种高效发现该解的通用途径。在这种设想下，人类将能够系统性地攻克当前面临的最严峻挑战（例如研制出攻克癌症的有效疗法）。正如 Wigderson 所总结，这种等价性意味着人类将有能力获知所有想要探索的知识，这是关乎人类认知能力极限的核心命题。 Wigderson 将复杂的计算理论转化为对人类知识极限的哲学反思。然而讨论聚焦于理论框架的宏观阐释与概念映射，并未深入涉及该数学命题在形式化证明层面的具体阻碍或技术进展。

Source quotes

[0:00] Avi Wigderson: So, the question of P versus NP is whether we can solve all the problems we want to solve, whether we can know everything we want to know.

Original transcript

[0:00] In one of your lectures, you mentioned [0:01] that P equals NP is philosophically [0:05] about the fundamental limits of human [0:07] knowledge. What is P equals NP, and how [0:12] does it relate to human knowledge? [0:14] >> Right in the [0:16] simplest way, and I will talk at a high [0:18] level. [0:20] Uh, we are interested in [0:23] various problems in life, and all sorts [0:25] of problems, mathematical problems, [0:27] scientific problems, medical problems, [0:30] personal problems, intellectual [0:32] problems. We are in the business in [0:34] computer science of solving problems by [0:36] computers. [0:37] Now, [0:39] uh, [0:40] we would like to somehow classify uh, [0:43] those problems that we can solve. [0:47] Right? To know what we can know. What [0:49] the problems we can solve are the things [0:51] we will know, we will understand. So, [0:53] there are all those problems that we [0:56] want to understand. There are many of [0:58] them. [0:59] Uh, and there are the problems that we [1:02] can understand, can solve. [1:04] Okay? [1:05] In a very basic way, the first class is [1:08] NP. All the problems we want to solve [1:10] are really NP problems. [1:13] So, it's a class of problems. [1:15] Uh, a subset of which is the problems we [1:18] can solve. They are the problems we can [1:20] currently solve, but we are interested [1:22] in all the problems we can solve [1:25] in principle, we can ever, you know, [1:28] really solve. So, the question of P [1:31] versus NP is whether we can solve all [1:35] the problems we want to solve, whether [1:37] we can know everything we want to know. [1:41] This is basically about the limits of [1:44] our knowledge. [1:45] Of course, I have to justify why, you [1:49] know, these classes, which are [1:50] mathematically defined, actually are [1:52] captured by these intuitive um, [1:56] intuitive meanings I'm giving them. P is [1:59] very easy to justify. What we can solve [2:01] is what we can [2:03] uh, you know, solve in our lifetime [2:05] using whatever we have, let's say all [2:07] computers that we uh, [2:09] have using efficient algorithms. So, [2:12] problems we can solve are problems you [2:14] see in our apps in our phones, like [2:17] if there's a navigation app, it means [2:19] somebody invented an algorithm that's [2:22] efficient enough to solve any you know, [2:25] shortest path problem between any and [2:27] any two places in any kind of map. [2:31] Okay. [2:32] Uh, why are all the problems we want to [2:35] solve are NP problems? [2:38] What is NP? NP is a class of problems, a [2:41] mathematical definition, uh, [2:45] problems so that, you know, whether [2:47] they're easy or hard to solve, we don't [2:49] know, but if somebody hands us a [2:52] solution, [2:53] then we can easily check that indeed it [2:56] is a good solution. [2:58] Now, why [2:59] are all problems we humanity is [3:02] interested in of this nature? You can [3:04] think there's no limit to what we may [3:06] want to know. [3:07] But I claim that essentially in any [3:10] human endeavor, the [3:13] if you're embarking on any problem, if [3:15] you really seriously want to solve a [3:16] problem, the least you want to know [3:20] is that when you hit upon a solution, [3:22] you'll recognize it as a solution. [3:25] I mean, why would you ever start on [3:27] looking for something if you would never [3:29] recognize it as [3:30] what you looked for? [3:32] So, you think mathematicians are [3:34] looking, uh, for proofs of theorems? [3:37] Certainly, if somebody gives a proof, [3:39] you know, wrote the paper about it, we [3:41] can verify. [3:42] If a scientist wants to explain data, [3:46] uh, you know, about the planets or [3:48] about, I don't know, [3:50] the, you know, bacteria or whatever, [3:53] uh, [3:54] you know, we want to develop a theory, [3:57] so that's what you're searching for in [3:58] this case. [4:00] And yeah, we again, scientists write [4:03] papers about their theories, they have [4:05] to be consistent with the data. We have [4:07] a way of recognizing that this is a good [4:10] solution. [4:11] Engineers [4:13] uh you know, are usually tasked with [4:16] creating something, bridge or phone or [4:19] you know, [4:20] something [4:22] uh under some constraints. It can be [4:24] monetary constraints, physical [4:26] constraints, all sorts of you can use [4:28] this but not this and so on. But anyway, [4:30] if an engineer designs something, [4:33] whoever gave them their task can look at [4:35] it and say, "Well, you you [4:37] violated some constraints." Or no, it's [4:39] good. You you you really delivered what [4:43] we were looking for. So, I'm giving you [4:45] examples. I mean, I can give many more. [4:47] Detectives are supposed to solve crimes [4:49] and you know, we know from detective [4:52] books, you know, they eventually [4:53] provide. So, [4:55] these are examples of very fundamental [4:58] human endeavors that are, you know, [5:00] encompass almost everything I can think [5:03] of. In all of them, what people are [5:05] searching for have the property that [5:07] when a solution is found, [5:10] it is easily recognized. [5:12] So, [5:14] uh repeating the beginning, NP are all [5:17] problems that we can honestly say we [5:20] really want to solve. And P are those [5:23] that we can solve. Whether they are [5:25] equal, you know, if they are equal, then [5:27] everything we would want to know, cure [5:29] for cancer, uh you [5:32] anything you imagine, [5:34] uh can be, uh you know, just the very [5:36] fact that [5:38] a solution can be easily recognized [5:40] would imply that it can be efficiently [5:42] found. [5:44] That means that we can know everything [5:46] we ever want to know. It's a fundamental [5:47] question about human knowledge.