What P vs NP is actually about

What P vs NP is actually about — Polylog

Polylog

AI-assisted summary of What P vs NP is actually about — original source. Check the original for full context.

Source published:

Key ideas

  • The P versus NP question fundamentally asks whether computational algorithms can be run in reverse as efficiently as they are evaluated forward. (0:01)
  • Any deterministic algorithm or digital circuit can be mechanically translated into a Boolean satisfiability (SAT) instance in Conjunctive Normal Form (CNF). (4:41)
  • By clamping the output wire of a multiplication circuit to a target value while leaving input wires unconstrained, a SAT solver acts as an integer factorer capable of breaking RSA. (6:49)
  • The Cook–Levin theorem established that SAT is NP-complete, proving that discovering a polynomial-time SAT solver would yield efficient solutions for all NP problems. (12:03)

Detailed notes

## Background Published by Polylog on YouTube on August 19, 2024, this video explores the core concepts underlying the P versus NP problem. According to the page description, it investigates what would happen if algorithms could be run backwards by converting programs into circuits and translating those into boolean satisfiability (SAT) problems.

## TL;DR The video reframes the P versus NP question around the concept of algorithmic invertibility—whether computational processes can be run backwards as easily as they run forward. By converting deterministic operations like multiplication or graph-coloring verification into digital circuits, every logical gate can be encoded into boolean satisfiability (SAT) clauses. Because constraints lack innate directionality, an efficient polynomial-time SAT solver would allow one to clamp output wires and invert any checking algorithm, cracking RSA cryptography and collapsing the entire NP complexity class. Ultimately, the piece explains the Cook–Levin theorem and Karp's reductions, showing how thousands of NP-complete problems are just disguised manifestations of SAT, while reflecting on why proving the intractability of inversion remains theoretical computer science's greatest challenge.

## Atmosphere & style The presentation carries Polylog's signature cerebral, highly visual, and lucid explanatory style, driven by calm narration and crisp, Solarized-palette Manim animations. It feels intellectually exhilarating yet deeply grounded, guiding the viewer from elementary logic gates to cosmic questions of entropy and computational asymmetry. Rather than drowning in abstract complexity theory, the video builds intuitive momentum through hands-on mechanical demonstrations, evoking both the playful wonder of reverse-engineering a circuit and the profound awe of facing a fundamental law of mathematical reality.

## Bulletin - [00:01](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=1s) The P versus NP question fundamentally asks whether computational algorithms can be run in reverse as efficiently as they are evaluated forward. - [04:41](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=281s) Any deterministic algorithm or digital circuit can be mechanically translated into a Boolean satisfiability (SAT) instance in Conjunctive Normal Form (CNF). - [06:49](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=409s) By clamping the output wire of a multiplication circuit to a target value while leaving input wires unconstrained, a SAT solver acts as an integer factorer capable of breaking RSA. - [12:03](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=723s) The Cook–Levin theorem established that SAT is NP-complete, proving that discovering a polynomial-time SAT solver would yield efficient solutions for all NP problems.

## Key takeaways - [00:01](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=1s) P versus NP is not just an abstract taxonomy of complexity classes; it centers on whether algorithms can be inverted as easily as they are computed. - [00:48](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=48s) The Boolean satisfiability problem (SAT) asks whether there exists a variable assignment of 0s and 1s that simultaneously satisfies a system of logical constraints. - [02:15](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=135s) RSA cryptography depends on the computational asymmetry between easy multiplication and the apparent hardness of factoring large composite integers. - [02:45](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=165s) Long multiplication in binary can be physically laid out as a circuit of logic gates, such as AND arrays for partial products and adder rows for summation. - [04:41](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=281s) Every individual logic gate can be faithfully encoded into Conjunctive Normal Form (CNF) clauses matching its truth table. - [06:49](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=409s) Because constraints have no inherent directionality, SAT solvers treat inputs and outputs identically, enabling circuits to be executed in reverse. - [07:25](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=445s) Setting a multiplication circuit's output wires to a number and solving for inputs forces the SAT solver to perform factorization, extracting non-trivial factors or proving prime unsatisfiability. - [08:10](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=490s) Factoring real-world RSA keys would generate circuits with tens of millions of variables, which choke modern heuristic SAT solvers. - [08:46](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=526s) Any deterministic algorithm maps to semiconductor gates and wires, meaning any problem verification procedure can be converted into a SAT instance. - [10:35](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=635s) Inverting the verification circuit for 3-coloring by clamping its output wire to 1 allows a SAT solver to discover valid graph colorings from scratch. - [12:03](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=723s) The complexity class NP comprises all decision problems whose candidate solutions can be verified in polynomial time. - [12:37](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=757s) The Cook–Levin theorem proved that SAT is NP-complete, meaning every problem in NP reduces to SAT in polynomial time. - [13:33](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=813s) Richard Karp showed that SAT reduces to dozens of foundational combinatorial problems, which eventually expanded into thousands of equivalent NP-complete problems. - [14:33](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=873s) If P = NP, all modern cryptography would collapse, including one-way cryptographic hash functions designed to act like digital blenders. - [15:32](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=932s) Unlike physics, which can adopt principles like the second law of thermodynamics as empirical laws of nature, computer science requires a rigorous mathematical proof to establish P ≠ NP.

## Detailed walkthrough ### [00:01](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=1s) Running Computers Backwards and the Power of SAT

The inquiry begins with a provocative thought experiment: what would happen if we could run computers backwards? While the question might sound like science fiction, it forms the exact core of the most celebrated and consequential open question in theoretical computer science, the P versus NP problem. Framed through this lens, P versus NP is not merely an abstract taxonomy of complexity classes; it is fundamentally an investigation into whether algorithmic processes can be inverted as easily as they are evaluated in the forward direction.

At the center of this machinery stands the boolean satisfiability problem, universally known as SAT. Within theoretical computer science, SAT occupies a legendary status—functioning as a kind of algorithmic superhero. Researchers have identified thousands of distinct problems equivalent to SAT, yet computer science remains fundamentally stumped on how to solve it efficiently. As narrator Václav Volhejn outlines, unlocking an efficient solution to SAT would permit running arbitrary computer circuits in reverse, unlocking capabilities that range from cracking modern public-key cryptography to reshaping our understanding of computation itself. As Volhejn asserts: “By the end of this video, you'll understand why the P vs NP question is ultimately about whether we can invert algorithms.”

[00:48](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=48s) Demystifying SAT and CNF Formulas

At its foundational level, the boolean satisfiability problem begins with a set of boolean variables, each restricted to two possible states: true or false (or, in the natural shorthand of programmers, 1 and 0). Alongside these variables comes a collection of logical constraints that must all simultaneously evaluate to true. While general SAT allows arbitrary, highly nested logical expressions, computer scientists standardly simplify the problem into Conjunctive Normal Form (CNF-SAT). In a CNF formulation, the problem is expressed as a conjunction of clauses, where each individual clause consists of variables or their negations joined strictly by OR operations.

Consider a concrete clause such as $(b \lor \neg c \lor \neg d)$. This single constraint dictates that for the clause to be satisfied, either variable $b$ must be assigned 1, or $c$ must be assigned 0, or $d$ must be assigned 0. An entire SAT instance consists of many such clauses chained together by AND operations; every single clause must be satisfied by a chosen assignment of zeros and ones across the variables. Finding a valid assignment—or formally determining that no valid assignment can possibly exist—becomes astronomically difficult as the number of variables and constraints grows. If someone were to discover a lightning-fast SAT solver, the repercussions would be seismic. As Volhejn emphasizes: “The answer is that it would absolutely destroy any intuition that we have about our universe.”

[02:15](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=135s) Breaking RSA: Multiplication as a Circuit

To understand the disruptive power of an efficient SAT solver, one need look no further than public-key cryptography. The world's digital infrastructure relies heavily on the RSA cryptosystem, whose mathematical shield rests on an asymmetry: multiplying numbers together is computationally trivial, whereas factoring a composite number into its constituent prime factors is believed to be exceptionally difficult. As Volhejn explains: “The security of the RSA cipher rests on the assumption that factoring, writing an input composite number as a product of two integers, is a really hard computational problem.” If factoring could be executed rapidly, RSA would crumble instantly.

Multiplying two numbers—such as 3 and 5—can be directly cast as an algorithmic problem and translated into a physical or logical circuit. Taking grade-school long multiplication and adapting it to binary (base 2), the algorithm operates by first computing intermediate products through bitwise operations and subsequently summing those partial products. In circuit form, this translates to a physical architecture of wires carrying electrical binary states (0 or 1) and logic gates performing primitive boolean operations.

```mermaid flowchart TD accTitle: Long Multiplication Circuit Architecture accDescr: Data flow showing input wires passing into intermediate product gates, then adder stages, to output product wires.

subgraph Inputs ["Input Layer"] A["Input A (e.g., 3 / 0011)"] B["Input B (e.g., 5 / 0101)"] end

subgraph Logic ["Circuit Core"] AND["AND Gate Array (Partial Products)"] ADD["Binary Full-Adder Rows (Summation)"] end

subgraph Output ["Result Layer"] OUT["Output Product Wires (e.g., 15 / 1111)"] end

A --> AND B --> AND AND --> ADD ADD --> OUT ```

For two 4-bit numbers, the circuit feeds the input wires through an initial bank of AND gates that generate the intermediate binary products. The second stage of the circuit passes those partial products through successive rows of binary adder gates—themselves constructed from elementary logic gates—to aggregate the totals. When 3 (`0011`) and 5 (`0101`) are set on the input wires and allowed to propagate forward through the gates, the output wires inevitably stabilize to the binary representation of 15 (`1111`).

[04:41](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=281s) Converting Digital Circuits into SAT Clauses

Because an algorithm implemented as a circuit is entirely governed by discrete local interactions, any digital circuit can be converted directly into a CNF-SAT instance. The conversion follows a clean, mechanical recipe: first, allocate a boolean SAT variable for every single wire across the circuit. Next, inspect each individual logic gate and write a set of boolean constraints that faithfully captures that gate's exact truth table.

For an AND gate where output wire $f$ is driven by input wires $c$ and $e$ ($f = c \land e$), its behavior is perfectly encoded using three CNF clauses: 1. $(\neg c \lor \neg e \lor f)$ 2. $(c \lor \neg f)$ 3. $(e \lor \neg f)$

The first clause enforces that whenever both inputs are 1 ($c = 1$ and $e = 1$), the terms $\neg c$ and $\neg e$ become 0, compelling wire variable $f$ to equal 1 to satisfy the clause. The subsequent two clauses enforce that if either input wire carries a 0, the output wire $f$ cannot be 1.

Applying this logic to the complete 4-bit binary multiplication circuit yields a SAT instance comprising approximately 80 variables and 400 logical constraints. If this formula is submitted to a SAT solver without fixing any inputs, the solver will simply search for any physically valid state of the circuit, returning an arbitrary valid multiplication (such as $2 \times 4 = 8$ or $1 \times 7 = 7$). However, if the user explicitly appends unit clauses pinning the input wire variables to specific bits—specifying that wire $x_1 = 0$, $x_2 = 1$, and so on—the SAT solver is constrained to a single unique solution. The solver propagates the logical implications, and reading the resulting values assigned to the output wire variables reveals the product: 15.

[06:49](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=409s) Running the Circuit in Reverse to Factor Numbers

Multiplying numbers by solving a massive system of SAT clauses is undeniably convoluted when a simple CPU instruction can do it in a fraction of a nanosecond. But the procedure harbors a transformative secret: constraints have no innate directionality. While a physical circuit can only propagate signals downstream from inputs to outputs, a SAT formulation treats every wire variable with equal mathematical standing.

Instead of freezing the input wires and letting the solver deduce the output, one can invert the constraints: clamp the output wires to 15, and leave the input wire variables completely unconstrained. By doing so, the user forces the SAT solver to work backwards through the multiplication network. Volhejn highlights the conceptual shift: “In other words, we're solving the question: if we know the output of the circuit is 15, what does its input have to be?” The solver is no longer multiplying; it is factoring.

- **Handling Trivial Factors:** Left unguided, a SAT solver attempting to factor 15 might promptly assign the input variables to 1 and 15 ($1 \times 15 = 15$). While mathematically valid, trivial factorizations do not break ciphers. To rule them out, one appends a handful of extra logic gates enforcing that both input factors must strictly exceed 1. - **Isolating Non-Trivial Factors:** With the non-triviality constraints integrated, running the SAT solver on output 15 cleanly extracts the inputs 5 and 3. - **Identifying Primes:** When provided an output corresponding to a prime number, such as 13, the SAT solver inspects the constraint network and reports that the instance is unsatisfiable (UNSAT), formally proving that no non-trivial factor pairs exist. - **The Gap to RSA:** Factoring the large composite keys typically found in RSA (roughly on the order of $10^{500}$) would yield a circuit requiring roughly 50 million variables. Modern heuristics-based SAT solvers choke on instances of that scale. However, if a polynomial-time algorithm—operating in linear or quadratic time—were discovered for SAT, breaking industrial RSA keys would become trivial.

[08:46](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=526s) General Reductions: Inverting Arbitrary Algorithms and Graph Coloring

The cryptographic breakthrough against RSA illustrates a universal principle. Nothing about the circuit-to-SAT conversion was unique to arithmetic multiplication. Any computer program running on standard hardware is ultimately executing on a microprocessor composed of semiconductor gates and wires. As Volhejn observes: “Ultimately, it's just a bunch of wires and gates.” Because any deterministic algorithm can be unfurled into a circuit of logic gates, any computational process can be mechanically translated into an equivalent SAT instance.

Consequently, having a general, rapid SAT solver would allow one to invert any algorithmic function imaginable. Standard computer execution asks: "Given input $X$, what is the output $Y$?" By contrast, encoding the circuit into SAT allows one to pose the inverse question: "Given that I desire output $Y$, what input $X$ must be supplied to generate it?"

This paradigm applies directly to classic hard computational challenges, such as the 3-coloring problem in graph theory. In 3-coloring, one is given an arbitrary graph and must color each node using one of three colors such that no two adjacent nodes share the same color. Verifying whether a proposed coloring is valid is computationally trivial: an algorithm simply iterates over every edge, checks whether the endpoints have different colors, and outputs 1 if valid or 0 if a conflict appears. But finding that coloring from scratch is notoriously difficult. By framing the simple verification algorithm as a circuit, fixing its output wire to 1 ("valid"), and handing the resulting formula to a SAT solver, the problem of finding a valid 3-coloring is automatically solved.

[10:35](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=635s) Inverting the 3-Coloring Checker via SAT

To verify a graph coloring, an algorithm simply iterates over all edges in the graph and checks that the endpoints of each edge are assigned distinct colors. Just like multiplication, this checking procedure can be translated directly into a boolean circuit. The resulting circuit looks considerably messier than the one used for integer multiplication, featuring dedicated logic gates for every single node and edge to confirm that no two adjacent vertices share the same color. A single final output wire indicates whether the coloring is valid; it evaluates to $1$ only if every single gate across the entire network confirms validity.

```mermaid flowchart LR accTitle: Inverting a Checking Circuit with SAT accDescr: A proposed coloring flows into a checking circuit, producing an output wire clamped to 1, which inverts verification into problem solving. subgraph Circuit["Verification Circuit"] A["Candidate Inputs<br/>(Color assignments)"] --> B["Logic Gates<br/>(Edges & Nodes)"] B --> C["Output Wire<br/>(1 = Valid, 0 = Invalid)"] end C -->|"Constrain output = 1"| D["SAT Solver<br/>(Inverts the circuit)"] D -.->|"Recovers"| A ```

If the circuit evaluates an invalid coloring, the output drops to $0$ because an internal NAND gate flags two adjacent vertices sharing an identical color. By encoding this circuit structure into a satisfiability (SAT) instance and attaching an explicit constraint requiring the final output wire to equal $1$, the verification algorithm is effectively inverted. Rather than merely validating a known coloring, the SAT solver is tasked with finding an input assignment that forces the checker to accept.

> “This gives us an incredibly general way of solving problems.”

- A verification circuit maps a candidate solution to a single boolean output ($1$ for valid, $0$ for invalid). - Clamping the output wire to $1$ within a SAT formulation forces the solver to search backward for valid inputs. - Any decision problem equipped with an efficient solution checker can have its inverse encoded as an instance of SAT.

---

[12:03](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=723s) P, NP, and Cook–Levin NP-Completeness

In theoretical computer science, a “fast” algorithm is formally defined as one whose runtime is bounded by a polynomial function of the input size. The complexity class NP consists of all decision problems whose candidate solutions can be verified in polynomial time. NP encompasses virtually all landmark computational challenges, ranging from 3-coloring and integer factorization down to simpler operations like integer multiplication. Because the reduction converting an arbitrary checking algorithm into a SAT formula runs in polynomial time, discovering a polynomial-time SAT solver would automatically yield a polynomial-time solution for every problem inside NP.

Crucially, the satisfiability problem itself belongs to NP. Checking whether an assignment satisfies a SAT formula is straightforward: one simply iterates through each clause to verify that all constraints evaluate to true. Because SAT is inside NP and every other problem in NP can be transformed into it, satisfiability acts as the "hardest" problem in the class. Formally, a problem is NP-complete if it sits in NP and every NP problem reduces to it in polynomial time. This foundational result was proven independently over 50 years ago by Stephen Cook and Leonid Levin.

> “So you can view satisfiability as the hardest problem in NP. Because once you've solved SAT, you've solved everything in this class.”

- **Fast algorithm:** An algorithm running in polynomial time. - **NP (Nondeterministic Polynomial time):** The class of problems where candidate solutions are verifiable in polynomial time. - **NP-completeness:** A problem is NP-complete if it is in NP and every problem in NP can be reduced to it in polynomial time. - **Cook–Levin Theorem:** Proved that SAT is NP-complete, establishing the foundation of computational complexity theory.

---

[13:33](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=813s) Karp’s 21 Problems and the Universality of SAT

Shortly after Stephen Cook proved that SAT is NP-complete, Richard Karp published a seminal paper demonstrating that the phenomenon was widespread. Karp established polynomial-time reductions from SAT to roughly 20 other central NP problems, including the traveling salesman problem and graph coloring. In the decades following Karp’s work, researchers identified thousands upon thousands of additional NP-complete problems across graph theory, combinatorial optimization, machine learning, bioinformatics, and game theory.

```mermaid flowchart TD accTitle: Equivalence of NP-Complete Problems accDescr: Cook and Levin proved SAT is NP-complete, Karp reduced SAT to 20+ problems, which expanded into thousands of equivalent NP-complete problems. A["Cook-Levin Theorem<br/>(Proves SAT is NP-Complete)"] --> B["Richard Karp's Reductions<br/>(20+ Problems, e.g., TSP, Coloring)"] B --> C["Thousands of Modern NP-Complete Problems<br/>(Optimization, Bioinformatics, ML, Games)"] C -->|"Polynomial-time algorithm for any single problem"| D["Universal Solution for ALL NP-Complete Problems"] ```

Because an efficient algorithm for any single NP-complete problem would immediately solve every other NP-complete problem via these polynomial reductions, their fundamental distinctness is open to debate. They can all be understood as alternative mathematical formulations of a single underlying puzzle: satisfiability.

> “They're all just different formulations of a single problem: satisfiability.”

---

[14:33](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=873s) P vs NP, One-Way Functions, and the Intuition of Inversion

The core question remains: does a polynomial-time algorithm for satisfiability exist? This is the famous P versus NP problem. In practice, the best general-purpose SAT solvers in the worst case perform barely better than brute-force exponential search, trying every possible assignment. Back in the 1960s, researchers had already noted that trying assignments sequentially fails on large instances. This computational barrier aligns with deep human intuition: verifying a proposed answer feels fundamentally easier than discovering it from scratch, just as executing a function in the forward direction does not mean its inverse can be computed quickly.

If $P = NP$, an efficient SAT solver would not only break RSA factoring but collapse all cryptography by enabling the inversion of cryptographic hash functions. Hash functions act as digital "blenders" (prompting the classic catchphrase, *“Will it blend? That is the question”*), performing convoluted bitwise manipulations that are easy to run forward but intractable to reverse from output bits alone. This asymmetry mirrors entropy and the second law of thermodynamics, where making a mess is far easier than reassembling the pieces:

> “Unfortunately, the difference between physics and computer science is that we can't simply declare P does not equal NP as a law of nature and claim our Nobel prize.”

Unlike empirical physics, theoretical computer science demands rigorous mathematical proof. While researchers have developed countless techniques for designing clever algorithms, proving lower bounds—that *no* fast algorithm can ever exist for a given problem—remains extraordinarily difficult. As the video concludes, the narrator emphasizes that the true core of P vs NP is algorithmic invertibility:

> “The heart of the problem is whether we can invert algorithms.”

Viewers are invited to explore the companion blog post, which covers clarifications and weirder extensions—such as interpreting deep learning backpropagation as an approximate circuit inverter—before the narrator closes with an earnest plea to like, subscribe, and support the channel on Patreon.

## Notable quotes > [14:33](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=873s) Unfortunately, the difference between physics and computer science is that we can't simply declare P does not equal NP as a law of nature and claim our Nobel prize.

> [12:03](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=723s) So you can view satisfiability as the hardest problem in NP. Because once you've solved SAT, you've solved everything in this class.

> [02:15](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=135s) The security of the RSA cipher rests on the assumption that factoring, writing an input composite number as a product of two integers, is a really hard computational problem. — Václav Volhejn

## Mentioned Polylog, P vs NP, Boolean Satisfiability Problem (SAT), Conjunctive Normal Form (CNF), RSA cryptosystem, Stephen Cook, Leonid Levin, Cook–Levin Theorem, Richard Karp, Karp's 21 NP-complete problems, Traveling Salesman Problem, 3-Coloring Problem, Václav Volhejn, Václav Rozhoň, Richard Hladík, Gabor Hollbeck, Manim, Intel 8008

## Video description What if we could run algorithms backwards? We discuss how we could do this by turning algorithms into circuits and encoding those into satisfiability problems. We then explain how it all connects to P vs NP.

Patreon: https://www.patreon.com/Polylog Website: https://polylog.cc

#somepi

0:48 Satisfiability 2:15 Breaking RSA 8:46 General reductions to SAT 12:03 P vs NP

Blog post: https://vasekrozhon.wordpress.com/2024/08/18/what-p-vs-np-is-actually-about/ Code for the animations: https://github.com/polylog-cs/np-completeness/ Blender clip: https://www.youtube.com/watch?v=qg1ckCkm8YI

Richard Hladík: Script editor, animator Gabor Hollbeck: Video recording, video editor Václav Rozhoň: Writer, animator Václav Volhejn: Narrator, animator, script editor

Thank you to our beta testers: Matěj, Honza, Filip

Animations: manim, a Python library https://docs.manim.community/en/stable/ Color palette: Solarized https://ethanschoonover.com/solarized/ Music: Thannoid by Blue Dot Sessions Pictures: * Intel 8008: https://www.righto.com/2016/12/die-photos-and-analysis-of_24.html * Stephen Cook: https://www.heidelberg-laureate-forum.org/laureate/stephen-a-cook/ * Leonid Levin: https://www.cs.bu.edu/fac/Lnd/ * Richard Karp: https://www.icsi.berkeley.edu/icsi/people/karp * Mick Jagger, Keith Richards: Wikipedia * Hash function circuit: https://www.academia.edu/download/31149146/498-497.pdf

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

中文简报

P与NP问题的真正核心 该视频围绕算法的可逆性概念重新审视了P与NP问题——即计算过程在反向运行时的效率是否能与正向运行时相同。通过将乘法或图着色验证等确定性操作转化为数字电路，每个逻辑门都可以编码为布尔可满足性（SAT）子句。由于约束条件本身没有固有的方向性，高效的多项式时间SAT求解器将允许人们固定输出线路并反转任何验证算法，从而破解RSA密码学并导致整个NP复杂度类崩溃。最终，该内容阐释了库恩-勒文定理（Cook–Levin theorem）和卡普的归约（Karp's reductions），展示了数千个NP完全问题其实只是SAT的伪装体现，同时也思考了为何证明反向求解的棘手性仍然是理论计算机科学的最大挑战。 P与NP问题从根本上探讨的是计算算法在反向运行时的效率能否与正向评估时一样高。 (0:01) 任何确定性算法或数字电路都可以机械地转换为合取范式（CNF）下的布尔可满足性（SAT）实例。 (4:41) 通过将乘法电路的输出线路固定为目标值，同时保持输入线路不受约束，SAT求解器即可充当能够破解RSA的整数分解器。 (6:49) 库恩-勒文定理确立了SAT是NP完全的，证明了如果发现多项式时间SAT求解器，将为所有NP问题提供高效的解法。 (12:03)

Reading summary

Narrator Václav Volhejn frames the P versus NP problem fundamentally as an inquiry into whether algorithmic processes can be inverted as efficiently as they are evaluated forward, with the boolean satisfiability problem (SAT) functioning as the central mathematical engine. Algorithmic Inversion and the SAT Formulation (0:01) The boolean satisfiability problem (SAT) assesses whether boolean variables restricted to true or false (1 or 0) can satisfy a collection of simultaneous logical constraints. In theoretical computer science, SAT instances are typically standardized into Conjunctive Normal Form (CNF-SAT), where clauses composed of OR-connected literals are chained entirely by AND operations. Finding a valid assignment across escalating numbers of variables and constraints, or formally determining that none exists, rapidly becomes computationally difficult. Critically, logical constraints possess no innate physical directionality. While standard computer execution drives inputs downstream into outputs, a SAT formulation assigns equal mathematical standing to every variable. By shifting the constraints rather than following a unidirectional signal flow, a SAT solver can determine what inputs are required to produce a specific target output, transforming a forward evaluation problem into an inverse search. Converting Hardware Circuits into Bidirectional Constraints (4:41) Because digital algorithms operating on microprocessors consist of wires and logic gates governed by discrete local interactions, any deterministic algorithm can be mechanically translated into a CNF-SAT formula. Each wire is assigned a boolean variable, and each gate's truth table is expressed through logical clauses. For example, an AND gate driving output wire f from inputs c and e is fully captured by three clauses: (¬c ∨ ¬e ∨ f), (c ∨ ¬f), and (e ∨ ¬f). A 4-bit binary multiplication circuit generates roughly 80 variables and 400 constraints. When input variables are pinned to specific numbers, the SAT solver propagates the logic forward to deduce the product. However, clamping the output wires to a product such as 15 while leaving input variables unconstrained forces the solver to work backwards, turning multiplication into integer factorization. Additional gates can exclude trivial factors like 1 and 15, while prime targets return an unsatisfiable (UNSAT) result. Volhejn notes that factoring an industrial RSA key of roughly 10^500 requires approximately 50 million variables—a scale that defeats current heuristic solvers, but would collapse instantly if a polynomial-time SAT algorithm were discovered. NP-Completeness and Universal Reductions (12:03) The complexity class NP contains all decision problems whose candidate solutions can be verified in polynomial time, encompassing tasks from integer factorization and multiplication to graph 3-coloring. Because an algorithm checking a proposed solution can be translated into a boolean circuit with a single output wire indicating validity (1 for valid, 0 for invalid), clamping that output to 1 in a SAT formula inverts the verification procedure into an automated problem solver. Over 50 years ago, Stephen Cook and Leonid Levin independently proved that SAT is NP-complete: it belongs to NP, and every problem in NP reduces to it in polynomial time. Shortly thereafter, Richard Karp demonstrated polynomial reductions from SAT to roughly 20 other landmark problems, an equivalence network that has expanded to thousands of modern NP-complete problems across bioinformatics, machine learning, and combinatorial optimization. Consequently, discovering an efficient, polynomial-time algorithm for SAT would immediately provide a polynomial-time solution for every problem in NP. Cryptographic Asymmetry and the Proof Barrier (14:33) The question of whether P equals NP centers on whether efficient verification implies efficient search. In practice, general-purpose SAT solvers encounter worst-case instances requiring near brute-force exponential runtime. This asymmetry underpins modern cryptography, including one-way hash functions that readily compute forward bitwise scrambles but remain computationally intractable to invert from output bits alone. While this computational gap intuitively mirrors physical entropy and the second law of thermodynamics—where scrambling systems is far easier than restoring them—theoretical computer science cannot adopt empirical observation as a law of nature. Volhejn stresses that unlike physics, establishing whether P equals NP demands rigorous mathematical proofs of lower bounds demonstrating that fast algorithms cannot exist, which remains an unsolved theoretical challenge. The P versus NP question fundamentally asks whether computation can be run backwards as easily as forwards. Although polynomial-time algorithmic inversion would collapse cryptography and solve thousands of equivalent NP-complete problems, theoretical computer science remains constrained by the profound mathematical difficulty of proving algorithmic lower bounds.

精炼阅读摘要

叙述者 Václav Volhejn 指出，理论计算机科学的核心未决难题“P 对 NP”（P vs NP），本质上探讨的是算法过程能否像正向评估那样被轻易地逆向执行。其核心纽带是布尔可满足性问题（SAT），若能实现多项式时间的 SAT 求解算法，任意计算机电路乃至通用检验算法都将被高效逆向求解。 计算的逆向运行与 SAT 核心地位 (0:01) P 对 NP 问题常被视作抽象的复杂度分类，但从操作视角来看，其本质是探讨计算过程是否具有可逆性。在正向计算中，由已知输入计算输出通常极其迅速；然而，如果已知期望输出反求所需输入，传统计算方式往往需要面临巨大的搜索空间。作为这一理论体系的核心，布尔可满足性问题（SAT）在计算机科学中占据基础地位。在合取范式（CNF-SAT）规范下，系统由布尔变量（0 或 1）和由“或”逻辑构成的子句组成，所有子句必须通过“与”逻辑同时得到满足。 研究人员已发现数以千计的重要计算问题与 SAT 等价，但至今未能找到能在所有情况下高效求解 SAT 的算法。Volhejn 指出，一旦找到极速求解 SAT 的通用方法，计算机便能够逆向运行任意电路，这不仅能瞬间攻破现代公钥密码系统，还将彻底颠覆人类对宇宙信息处理规律的直觉认知。 电路到命题的转译与约束无向性 (4:41) 任何在标准计算机硬件上运行的确定性算法，微观上都是由半导体逻辑门和导线组成的物理或逻辑电路。以 4 位二进制整数乘法为例，算法首先利用与门阵列计算中间部分积，随后通过全加器门电路逐行累加，最终使输出端稳定呈现乘积结果。例如，输入 3（二进制 0011）与 5（二进制 0101），正向传输后输出端必然得出 15（二进制 1111）。 这类由离散局部交互构成的电路可机械化转译为 SAT 实例：为电路中每根导线分配一个布尔变量，并根据逻辑门的真值表编写 CNF 约束。例如，对于由输入导线 c、e 驱动输出导线 f 的与门，可精确拆解为三个子句进行约束。完整的 4 位乘法电路由此转化为包含约 80 个变量与 400 个逻辑子句的公式。关键在于，物理电路中信号只能从输入单向流向输出，但数学上的 SAT 约束没有任何内在方向性。若固定输入导线，求解器将正向推导出乘积；但若反向固定输出导线并放开输入变量，约束网络便会迫使求解器反向寻找输入。 逆向分解与通用解检验器的转化 (6:49) 约束无向性的直接应用之一是反向破解大整数乘法，即因数分解。在 4 位乘法转译的 SAT 模型中，若将输出端导线固定为 15，并附加额外门电路排除因子为 1 的平凡解，SAT 求解器便会自动逆向推导出输入为 3 和 5；若对质数 13 进行求解，系统则会判定公式不可满足（UNSAT），证明其不存在非平凡因子。现代 RSA 密码系统的安全性完全建立在乘法极其容易而大整数质因数分解极难的不对称假设上。破解约 10 的 500 次方规模的工业级 RSA 密钥大约需要构建包含 5000 万个变量的电路，现代启发式求解器无法承受该规模；但只要出现多项式时间的 SAT 求解算法，破解此类密码便会轻而易举。 这种逆向机制具有完全的通用性。任何可行的计算机检验程序均可编译为电路。在图论经典的 3 着色问题中，验证一组着色方案只需遍历所有边并确认端点异色，该过程可转译为输出单一验证位（1 为合法，0 为冲突）的电路。只需将该电路编码为 SAT 实例并将最终输出位强制固定为 1，SAT 求解器在反向搜寻满足条件的输入时，便自动完成了寻找合法着色方案的计算过程，从而将“解的验证”直接逆转为“解的构造”。 Cook–Levin 定理与 NP 完全性结构 (12:03) 在计算复杂性理论中，NP 类涵盖了所有能在多项式时间内验证候选解正确性的决策问题，包括 3 着色、因数分解以及基础乘法等。因为任何多项式时间验证算法均可在多项式时间内转化为等价的 SAT 逻辑公式，所以攻克 SAT 即意味着攻克整个 NP 类。Stephen Cook 与 Leonid Levin 在 50 多年前独立证明，SAT 本身属于 NP，且 NP 中的所有问题均可多项式时间归约至 SAT，由此确立了 SAT 作为首个“NP 完全”（NP-complete）问题的地位。 随后，Richard Karp 证明 SAT 可进一步多项式归约至旅行商问题、图着色等 20 多个核心问题。如今，研究人员已在组合优化、机器学习、生物信息学和博弈论中发现了数以千计的 NP 完全问题。这些表面迥异的问题在本质上均可被视作布尔可满足性这同一个核心谜题的不同数学表达形式，任何一个问题的多项式时间突破都将引发连锁反应，直接解决全部 NP 完全问题。 人类日常经验与物理直觉表明验证往往远比创造容易，如同打碎物体极易而复原极难、加密哈希函数正向运算极快而求逆极其困难。然而，与物理学不同，计算机科学无法将 P 不等于 NP 直接作为自然定律采纳，而必须给出严谨的数学证明。由于证明算法复杂度下界极其困难，算法究竟能否在本质上被全面逆向执行，至今仍是理论科学中未解的核心谜题。

Detailed notes — zh

## Background 该视频由 YouTube 频道 Polylog 于 2024 年 8 月 19 日发布。视频简介指出，本期内容探讨了如果我们能够将算法“倒着运行”会发生什么，通过把算法转换为布尔逻辑电路并编码为可满足性（SAT）问题，进而揭示这一机制与理论计算机科学核心难题 P vs NP 之间的深刻联系。 ## TL;DR 视频从“算法能否求逆”的独特视角重新审视了 P vs NP 问题。作者首先演示了如何将长乘法转化为布尔电路并编码为 SAT 约束，展现出通过强制固定输出端来反向求解因数分解、从而攻破 RSA 密码的理论可能。接着，视频将这一框架推广到图的 3-着色等 NP 问题的验证算法上，阐明了库克-列文定理的直观本质：任何验证过程都能转化为多项式规模的电路并归约为 SAT 问题。最终，视频指出寻找多项式时间 SAT 求解器的困境揭示了人类在“正向计算”与“逆向还原”之间的巨大认知鸿沟，而证明算法下界的极端困难正是 P vs NP 至今未解的核心根源。 ## Atmosphere & style 视频整体呈现出极具启发性、严谨且优雅的硬核科普质感。叙事节奏层层递进，借由 Manim 打造的精美动画将抽象晦涩的布尔逻辑门与复杂连线化繁为简，带来豁然开朗的智性愉悦。解说员 Václav Volhejn 的语调沉着从容，既巧妙融入了破壁机搅拌、热力学熵增等生动比喻与幽默调侃，又在探讨物理直觉与数学严格证明的鸿沟时展现出深邃的学术敬畏感。 ## Bulletin - [00:01](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=1s) P vs NP 问题的核心本质在于探讨计算机算法能否被高效地“倒向运行”，即从输出反推原像输入。 - [02:15](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=135s) 任何确定性算法均可转换为布尔逻辑电路并机械化编码为 CNF-SAT 问题，若拥有高效 SAT 求解器即可直接通过逆向求解电路来攻破 RSA 等公钥密码体系。 - [12:03](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=723s) 斯蒂芬·库克与列昂尼德·列文证明了 SAT 问题的 NP 完全性，随后理查德·卡普等证明了数千个经典计算难题本质上都是 SAT 的不同表达形式。 - [14:33](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=873s) 现代密码学与物理直觉严重依赖单向性假设（如哈希函数类似破壁机打碎物体难以复原），而证明 P ≠ NP 的真正瓶颈在于人类缺乏证明“复杂度下界”的数学工具。 ## Key takeaways - [00:01](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=1s) P vs NP 问题在概念上可以等价理解为：我们是否能够高效地实现“算法求逆”。 - [00:48](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=48s) 可满足性问题（SAT）是计算复杂性中的核心问题，求解即为寻找一组布尔变量赋值以满足所有逻辑约束（子句）。 - [02:15](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=135s) 任何可以在计算机上运行的确定性算法，都可以严格展开为由导线和基本逻辑门（AND、OR、加法器等）构成的布尔电路。 - [02:15](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=135s) 布尔电路能被机械化转换为合取范式（CNF-SAT）：为每根导线分配变量，为每个门分配等价的 CNF 子句约束。 - [02:15](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=135s) 通过在 CNF-SAT 中固定输出端数值而非输入端，SAT 求解器被强制用来执行反向计算；例如将乘法电路输出固定为大复合数即可转化为质因数分解问题。 - [02:15](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=135s) 对现代 RSA 规模（约 10⁵⁰⁰）的数进行分解对应的 SAT 实例约包含 5000 万个变量，若存在多项式时间 SAT 求解器将彻底破解 RSA。 - [08:46](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=526s) 物理电路无法违反物理法则逆向传导信号，SAT 求解的本质是在数学层面上计算函数 y = f(x) 的逆映射原像。 - [10:35](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=635s) 图的 3-着色问题可以构建为一个以着色方案为输入、输出单比特判断合规性的布尔电路。 - [10:35](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=635s) 将验证算法电路的输出导线强制约束为 1 并交给 SAT 求解，即可将所有“易于验证”的判定问题转化为求解输入方案的原问题。 - [12:03](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=723s) 所有解可以在多项式时间内得到验证的问题集合被定义为 NP 类，包含图着色、因数分解和旅行商问题等大量实际难题。 - [12:03](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=723s) 将验证算法转化为 SAT 实例的过程只需多项式时间，因此只要攻克多项式时间的 SAT 求解器，就能一次性解决整个 NP 类问题。 - [12:03](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=723s) 库克-列文定理证明了 SAT 的 NP 完全性（NP-complete），理查德·卡普等后续工作证明了成千上万个 NP 完全问题本质上都是 SAT 的不同马甲。 - [14:33](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=873s) 人类在直觉上深刻感知“验证一个解”与“从零寻找一个解”的不对称性，这种不对称性构成了单向函数（如哈希函数）和现代密码学的基石。 - [14:33](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=873s) 计算机科学不能像物理学根据热力学第二定律直接将 P ≠ NP 视为公理，其未解的根本症结在于缺乏证明“问题绝不可能存在快速算法”的严格数学下界工具。 ## Detailed walkthrough ### [00:01](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=1s) 倒转算法与 SAT 问题的终极视角 如果计算机能够“倒着运行”，世界会变成什么样？计算机科学中最著名的问题 P vs NP，其核心本质其实正是关于我们能否在计算上实现“算法求逆”。 可满足性问题（Satisfiability，简称 SAT）堪称算法问题世界中的“超级英雄”。人类已经发现了关于它的数千种等价表述，但至今仍不知道该如何高效地求解它。如果拥有一个超级快速的 SAT 求解器，其带来的震荡将远超技术本身，甚至会彻底颠覆常理。主讲人强调：“The answer is that it would absolutely destroy any intuition that we have about our universe.” 在形式化定义中，SAT 包含若干布尔变量（通常取值为 True 或 False，而在程序员眼中即 1 和 0），以及施加在这些变量上的逻辑约束。一般性的 SAT 允许任意复杂的逻辑公式，但通常讨论的是 CNF-SAT（合取范式 SAT）。在 CNF-SAT 中，每个约束（子句）由若干变量或其非形式通过“或”（OR）连接而成；例如约束 $(b \lor \neg c \lor \neg d)$ 意味着 $b$ 必须为 1、或者 $c$ 必须为 0、或者 $d$ 必须为 0。求解的任务就是为所有变量赋值，使得每一个约束同时得到满足（计算结果全为 1）。对于大规模的 SAT 实例，求出可行解或判定无解，在计算上是极其困难的问题。 ### [02:15](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=135s) 乘法电路与通过 SAT 破解 RSA RSA 密码系统的安全基石在于计算假设：大整数质因数分解（Factoring）在计算上极为困难。然而，因数分解的逆问题是整数乘法，而乘法是极其容易且广为人知的。以小学生都会的长乘法为例（在计算机底层以二进制基底运行），计算两数乘积的过程是先计算部分积，再逐行累加。 任何这种确定性算法都可以转换为由导线（Wire）和逻辑门（Gate）组成的布尔电路（Circuit）。在电路中，信号沿着导线在门之间传递并输出结果。比如两个 4 位的二进制数相乘（以 $3 \times 5 = 15$ 为例）： 1. 输入端由两组导线分别代表输入的两个 4 位二进制数（3 编码为 0011，5 编码为 0101）； 2. 电路前段由若干与门（AND）构成，计算长乘法中的部分积； 3. 电路后段通过由基本逻辑门构成的全加器（Adder gates）逐行累加中间结果； 4. 输出导线最终呈现二进制结果（15 编码为 1111）。 ```mermaid flowchart LR accTitle: 乘法电路与 SAT 逆向求质因数流程 accDescr: 展示了从输入数字到构建电路，再将电路转化为 SAT 约束并反向固定输出求因数的全过程。 subgraph Circuit["布尔电路逻辑"] A["输入导线 (X)"] --> B["AND 逻辑门 (计算部分积)"] B --> C["全加器加法门 (逐行求和)"] C --> D["输出导线 (Y)"] end subgraph Encoding["SAT 编码与求逆"] D -.->|"转为 400 个 CNF 约束"| E["SAT 问题实例"] F["正向运算: 固定输入 X"] --> E G["逆向分解: 固定输出 Y=15"] --> E E --> H["SAT 求解器"] H -->|"求解变量赋值"| I["得到因数 3 和 5"] end ``` 将电路转换为 SAT 问题的方法非常优美且机械化：为电路上每一根导线分配一个布尔变量，再将每一个逻辑门转换为等价的 CNF 子句。例如对于一个输出导线为 $f$、输入导线为 $c$ 和 $e$ 的与门（$f = c \land e$），可以用以下三个逻辑子句精确约束： * $(\neg c \lor \neg e \lor f)$：保证了当 $c=1$ 且 $e=1$ 时，$f$ 必须为 1； * $(c \lor \neg f)$ 与 $(e \lor \neg f)$：保证了只要 $c=0$ 或 $e=0$，$f$ 就必须为 0。 对于一个 4 位的乘法电路，大约需要 80 个变量和 400 个约束。若直接将这些约束丢给 SAT 求解器，求解器仅能保证各导线电平符合某种合法乘法，解并不唯一。但只要加入额外的单元子句把输入导线固定为 3 和 5，解便唯一定格在 $15$。 而真正的威力在于“颠倒因果”： * **反向固定输出**：不再固定输入导线，而是通过约束将输出导线直接固定为 15（即二进制 1111）。 * **求解因数分解**：SAT 求解器被强制回答一个问题：“要想输出端为 15，输入端必须是什么？”。这正是因数分解问题。 * **规避平凡解与素数判定**：求解器最初可能会给出平凡解 $15 = 1 \times 15$；但只需在电路中增加少量比较门，强制要求两个因子都必须大于 1，求解器便精准吐出了 $5 \times 3$。如果把输出固定为 13，SAT 求解器会直接返回无解（UNSAT），因为 13 是素数。 现代 RSA 所依赖的密钥大约需要分解 $10^{500}$ 级别的庞大数字。按照上述方法转换出的 SAT 实例将包含大约 5000 万个变量，这完全超出了当前工业级 SAT 求解器的承受极限。然而正如主讲人所指出的那样：“But the point is that if we did have a solver that could run in, say, linear or quadratic time, we would be able to use it to break RSA.” - 4 位乘法器转换为 CNF-SAT 需使用约 80 个变量与 400 个约束子句。 - 分解 $10^{500}$ 规模的 RSA 复合数对应约 50,000,000 个变量的 SAT 实例。 ### [08:46](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=526s) 万能求逆机制与图的 3-着色问题 分解因数的成功揭示了一个更为惊人的本质规律：乘法算法能够通过小规模电路实现，而 SAT 能够把这个前向计算电路“倒过来求解”。 主讲人明确指出，物理电路本身不可能在物理定律上逆着走，而这也正是 SAT 之所以极其困难的原因：“Of course, you can't literally run a circuit backwards, that's why the satisfiability problem is so hard.” 更精确的理解是将电路视为一个计算数学函数 $y = f(x)$ 的工具，SAT 编码本质上是在表达它的逆映射关系。即便面对多对一映射（多个输入对应同一输出），SAT 求解器也会自动寻找到其中一个合法原像。 任何在现代计算机上运行的算法，其物理底座不过是 CPU 内部成千上万的导线与逻辑门。因此，**任何算法都可以被等价展开为一个布尔电路**。这就赋予了我们一种近乎全能的机制：我们不仅能回答常规的“输入给定时输出是什么”，更能通过 SAT 编码向计算机提问：“如果我想要某个特定的输出，我究竟需要提供什么样的输入？” 这种“算法求逆”框架构成了 NP 问题的核心。以图的 3-着色问题（3-Coloring）为例：给定一个图，要求用三种颜色为每个节点涂色，使得任意相邻节点的颜色都不相同。如果有人给出一个着色方案，验证其是否正确非常容易（只需检查每条边两端的颜色）；而寻找一个合法的着色方案，正是要求我们将这个快速验证程序“倒过来跑”，推导出满足“输出为有效”的输入着色。 ### [10:35](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=635s) 将图着色验证算法转化为电路与 SAT 问题 图着色问题的验证过程非常直观：只需遍历图中的所有边，确保每条边两端的顶点颜色不同即可。然而，一旦将这个看似简单的验证算法转化为布尔逻辑电路，其线路之复杂甚至超过了乘法电路。为了理清思路，可以将大部分杂乱的连线淡出。电路的核心逻辑是为图中的每个节点和每条边设置对应的门电路，整套门电路协同工作，共同检查整张图上的所有边是否都满足着色要求。 这一复杂电路最终只汇聚成一根输出导线。当所有内部门电路都输出 1 时，该导线输出 1，表明当前的着色方案是合法的；若有任何一条边两端的顶点颜色相同，对应的与非门（NAND gate）就会检测到错误，导致最终输出为 0。为了反转该检验过程，只需将整个电路编码为一个可满足性问题（SAT 问题），并在其输出端添加一个强约束：输出必须为 1。通过这种方法，“The SAT instance now asks to find a set of inputs that the coloring checker will accept.”（解说员 Václav Volhejn 指出：“现在的 SAT 实例要求找出能被着色检验器接受的一组输入。”）这本质上就完成了 3-着色问题（3-Coloring）的求解编码。 ```mermaid flowchart LR accTitle: 将检验算法反转为 SAT 问题的流程 accDescr: 展示从输入方案、电路检验、约束输出为 1 到求解原问题的完整路径 subgraph Verification ["验证阶段"] A["候选输入方案"] --> B["布尔门电路系统"] B --> C{"输出导线: 是否合法?"} end subgraph Inversion ["反转求解阶段"] C -->|"强制约束 Output = 1"| D["编码为 SAT 实例"] D --> E["运行 SAT 求解器"] E --> F["输出合法解 (反向求出原问题解)"] end ``` 这种转化的威力在于它的普适性。对于任何只要能通过验证算法快速检查解答正确性的问题，都可以利用这个技巧，将其检验函数的逆函数编码为一个 SAT 问题。由于这个逆函数的作用是将输出端满足的“YES”映射回一个合法的输入解，这便赋予了我们一种极具普适性的问题求解范式。 --- ### [12:03](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=723s) P 与 NP 的定义及 SAT 问题的 NP 完全性 理论计算机科学中，将运行时间复杂度为多项式函数的算法严格定义为“快速算法”。所有解的正确性可以在多项式时间内得到验证的问题集合，被称为 NP 类（Nondeterministic Polynomial time）。这一类别囊括了计算机科学中绝大部分核心难题，诸如图着色、整数分解（RSA 的基石），甚至包括简单的两数相乘。 将任何检验算法转化为 SAT 电路的过程本身是在多项式时间内完成的。这意味着，只要存在一个能在多项式时间内运行的 SAT 求解器，就等于为 NP 类中的所有问题都找到了多项式时间的解决方案。有趣的是，SAT 问题自身也恰好属于 NP 类——检验一组变量赋值是否满足 SAT 公式极其容易，只需逐一核对每项约束条件即可。因此，SAT 可以被视作 NP 类中最困难的问题：“Because once you've solved SAT, you've solved everything in this class.”（解说员表示：“因为一旦你解决了 SAT，你就解决了该类别中的一切问题。”） - **NP 完全（NP-complete）的定义**：一个问题若属于 NP 类，且所有其他 NP 问题都能在多项式时间内归约（reduce）到该问题，则称该问题为 NP 完全问题。 - **库克-列文定理（Cook-Levin Theorem）**：50 多年前，斯蒂芬·库克（Stephen Cook）与列昂尼德·列文（Leonid Levin）各自独立证明了 SAT 问题是 NP 完全的，奠定了理论计算机科学最重要的基石之一。 - **理查德·卡普（Richard Karp）的扩展**：在库克之后，卡普发表了一篇著名论文，通过归约技巧证明了包括图着色、旅行商问题（TSP）在内的 20 多个著名问题全都是 NP 完全问题。 - **NP 完全问题的本质统一性**：后续研究在图论、优化、机器学习、生物信息学甚至各类博弈游戏中发现了成千上万个 NP 完全问题。从理论角度来看，这些问题本质上都是同一个问题——可满足性问题（SAT）的不同表达形式。 --- ### [14:33](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=873s) P vs NP 的核心：能否将算法“倒着运行”？ 既然所有 NP 完全问题都等价于 SAT，核心疑问随之而来：SAT 问题究竟是否存在多项式时间算法？这就是举世闻名的“P 与 NP 问题”（P vs NP）。目前业界最优秀的 SAT 求解器在最坏情况下依然无法摆脱暴力遍历所有可能赋值的指数级时间。虽然暴力破解可以应对小规模实例，但早在 1960 年代计算机科学家们就已指出，单凭穷举试错绝不可能攻克大规模问题。 人类对于“验证一个给定的解”和“从零找出该解”之间存在着巨大的直觉鸿沟。换句话说，即使一个函数能够被快速计算，它的逆函数也未必能被快速计算。一个多项式时间的 SAT 求解器不仅会彻底颠覆这一直觉，还会直接击垮现代密码学的基础。密码学中广泛依赖的单向函数（如哈希函数）正如同一台破壁机（Blender）：“Will it blend? That is the question.”（视频借用经典网络梗调侃道：“它能打碎吗？这是个问题。”）哈希函数通过对输入比特施加极度混乱的混合运算，使得从输出反推输入变得极端困难。这类似于物理学中熵增与热力学第二定律——把东西打碎容易，将碎片复原却难如登天。 然而计算机科学与物理学的区别在于，我们不能直接把“P 不等于 NP”宣布为一条自然法则然后去领诺贝尔奖。在数学上，快速的 SAT 求解器仍有存在的理论可能，我们只是在直觉上认为它极不可能。之所以至今未能证明 $P \neq NP$，根本症结在于：人类拥有许多设计精巧算法的技巧，却极度匮乏“证明某个问题绝不可能被快速算法解决”的下界证明工具。 解说员最后强调，探究 P 与 NP 问题的灵魂所在，就是探究算法是否能够被无损、高效地“反向运行”。在片尾的致谢与花絮中，团队顺带提到了博客文章中的前沿延伸思考——深度学习的成功在某种程度上甚至可以通过反向传播算法（Backpropagation）来理解，因为反向传播的本质就像是一种在特定条件下“反转电路”的算法。解说员打趣道，虽然请求观众点赞订阅显得有些俗套（“Ah, that's so cheesy, isn't it?”），但仍真诚感谢观众在 Patreon 上的支持。 ## Notable quotes > [08:46](https://www.youtube.com/watch?v=6OPsH8PK7xM&t=526s) Of course, you can't literally run a circuit backwards, that's why the satisfiability problem is so hard. — 主讲人 ## Mentioned P vs NP, SAT, CNF-SAT, RSA, Stephen Cook, Leonid Levin, Richard Karp, 3-Coloring, TSP, Polylog, Václav Rozhoň, Václav Volhejn, Richard Hladík, Gabor Hollbeck, Intel 8008, Manim, Patreon ## Video description What if we could run algorithms backwards? We discuss how we could do this by turning algorithms into circuits and encoding those into satisfiability problems. We then explain how it all connects to P vs NP. Patreon: https://www.patreon.com/Polylog Website: https://polylog.cc #somepi 0:48 Satisfiability 2:15 Breaking RSA 8:46 General reductions to SAT 12:03 P vs NP Blog post: https://vasekrozhon.wordpress.com/2024/08/18/what-p-vs-np-is-actually-about/ Code for the animations: https://github.com/polylog-cs/np-completeness/ Blender clip: https://www.youtube.com/watch?v=qg1ckCkm8YI Richard Hladík: Script editor, animator Gabor Hollbeck: Video recording, video editor Václav Rozhoň: Writer, animator Václav Volhejn: Narrator, animator, script editor Thank you to our beta testers: Matěj, Honza, Filip Animations: manim, a Python library https://docs.manim.community/en/stable/ Color palette: Solarized https://ethanschoonover.com/solarized/ Music: Thannoid by Blue Dot Sessions Pictures: * Intel 8008: https://www.righto.com/2016/12/die-photos-and-analysis-of_24.html * Stephen Cook: https://www.heidelberg-laureate-forum.org/laureate/stephen-a-cook/ * Leonid Levin: https://www.cs.bu.edu/fac/Lnd/ * Richard Karp: https://www.icsi.berkeley.edu/icsi/people/karp * Mick Jagger, Keith Richards: Wikipedia * Hash function circuit: https://www.academia.edu/download/31149146/498-497.pdf [Source](https://www.youtube.com/watch?v=6OPsH8PK7xM)

Source quotes

[8:46] 主讲人: Of course, you can't literally run a circuit backwards, that's why the satisfiability problem is so hard.

Source quotes

[14:33] Unfortunately, the difference between physics and computer science is that we can't simply declare P does not equal NP as a law of nature and claim our Nobel prize. [12:03] So you can view satisfiability as the hardest problem in NP. Because once you've solved SAT, you've solved everything in this class. [2:15] Václav Volhejn: The security of the RSA cipher rests on the assumption that factoring, writing an input composite number as a product of two integers, is a really hard computational problem.

Original transcript

[0:01] Ever wonder if we could run computers backwards? [0:04] Today we'll be looking at the most famous problem in computer science, [0:07] P vs NP, from this unusual angle. [0:09] By the end of this video, you'll understand why the P vs NP [0:12] question is ultimately about whether we can invert algorithms. [0:17] First, we'll meet satisfiability, or SAT for short, a kind of superhero [0:22] among algorithmic problems. [0:24] We know literally thousands of equivalent definitions of it, and we [0:27] still have no idea how to solve it. [0:29] Next, we'll break a famous cipher by building a multiplication circuit [0:33] and using SAT to run it backwards. [0:35] Finally, we'll see how the idea of inverting algorithms connects [0:39] to the most important question in computer science, P versus NP. [0:48] Our story starts with the satisfiability problem, also known as SAT. [0:52] This is an incredibly powerful problem. [0:55] We'll see that, if we could solve it efficiently, we could [0:57] use it to reverse any algorithm. [1:00] Let's see what the problem is about. [1:02] We're given a bunch of boolean variables, meaning each can be [1:05] set to either true or false. [1:07] But since I'm a programmer, I'll write 1 and 0 instead. [1:11] We're also given a bunch of logical constraints on those variables [1:14] that have to be satisfied. [1:16] In the general SAT problem, a constraint can be an arbitrarily [1:19] complex logical formula like this. [1:21] But for simplicity, we'll only consider the so called CNF SAT. [1:26] In this variant, each constraint is a bunch of variables or their [1:29] negations that are connected by OR. [1:32] So, for example, this constraint says that either b must be 1, [1:36] or c must be 0, or d must be 0. [1:40] The task is to set the values of the variables to satisfy [1:43] all of the constraints. [1:45] This specific choice works because if we plug these values into our [1:48] constraints and simplify, Every constraint evaluates to 1, meaning it's satisfied. [1:53] Given a large satisfiability problem, solving it, or figuring [1:56] out that there is no solution, is a really hard computational problem. [2:00] But let's make the following thought experiment. [2:03] Let's say we do have a really fast SAT solver. [2:06] Would such an algorithm have any interesting implications? [2:09] The answer is that it would absolutely destroy any intuition [2:13] that we have about our universe. [2:15] To start with the tip of the iceberg, let's see how we could use this [2:18] fast SAT solver to break perhaps the most famous cipher of all, RSA. [2:24] The security of the RSA cipher rests on the assumption that factoring, [2:28] writing an input composite number as a product of two integers, is a [2:32] really hard computational problem. [2:33] As far as we know, that is the case, but if we had a really fast SAT solver, [2:38] we could suddenly solve factoring. [2:40] Let's see why. [2:41] First, let's talk about the inverse problem to factoring, multiplication. [2:46] Let's say you want to multiply two really large numbers, like three and five. [2:52] We can reduce this problem to SAT. [2:55] We're going to utilize the long multiplication algorithm [2:57] you know from school. [2:59] You've learned it for base 10 numbers, but we'll use it in base 2. [3:03] So let's convert the numbers 3 and 5 to binary and run the algorithm. [3:07] We first compute the intermediate products and then sum them up. [3:11] To convert this algorithm to a SAT instance we'll think about [3:14] it as a so-called circuit. [3:16] A circuit is simply a bunch of wires that can propagate a signal and gates [3:20] that apply simple logical functions. [3:22] You can fix the value of each input wire to 1 or 0. [3:26] Then the signal propagates through the wires and the gates and you can read [3:30] the output off of the wires at the end. [3:33] Coming back to our multiplication algorithm This is how you [3:36] represent it as a circuit. [3:38] You can see that there are two sets of input wires that hold two 4-bit numbers. [3:42] We can now encode the numbers 3 and 5 as inputs to the circuit and let it run. [3:49] The first part of the circuit uses AND gates to compute the intermediate product. [3:54] You can see how the values of the gates correspond to the intermediate values [3:57] in the long multiplication algorithm. [4:00] The second part of the circuit sums those results up. [4:03] Each row of adder gates adds the next intermediate result to the total. [4:08] Finally, we can look at the output wires to get the result [4:11] and find that 3 times 5 equals... [4:15] 15! [4:16] This special plus gate in the circuit is just a shorthand to [4:20] make the circuit more readable. [4:23] The gate performs a simple addition in binary. [4:26] This is how you can implement it using elementary logical gates. [4:30] You can pause to work out how the other gates and the overall circuit works, but [4:34] the exact details are beside the point. [4:36] What matters is that we can convert the long multiplication [4:39] algorithm to a circuit. [4:41] Now, let's see how we can convert a circuit to a SAT instance. [4:45] Let's take a simpler example first. [4:47] We create a variable for each wire in this circuit. [4:50] Next. [4:51] Consider any gate like this one that says that the value of f is equal to c and e. [4:57] We can encode the logic of this gate with the following three constraints. [5:01] Let's start with the first one. [5:02] On the one hand, if either c or e are set to 0, the constraint is going [5:07] to be satisfied because not 0 is 1. [5:10] On the other hand, if both c and e are set to 1, the constraints becomes 0 or 0 or f. [5:17] So the only way to satisfy it is to set f to 1. [5:21] If you think about it, this constraint encodes the fact that if both of [5:25] the inputs to the AND gate are 1, the gate will also return 1. [5:30] Similarly, the other two constraints encode the logic of the AND gate [5:33] when one of the inputs is 0. [5:36] We can do the same thing for all gates. [5:38] And by taking all these constraints together, we've managed to [5:41] represent the logic of the original circuit as a SAT problem. [5:45] Let's do the same for our multiplication circuit. [5:47] In this case, we need around 80 variables and 400 constraints. [5:51] What happens if we feed this into a SAT solver? [5:54] Well, the solver ensures that all the values on the wires correspond to [5:58] the circuit being run on some input. [6:00] Remember that SAT problems can have multiple solutions. [6:03] Our constraints don't specify any particular input to the algorithm, [6:07] so there are many solutions, each one corresponding to the algorithm [6:10] being run on some two numbers. [6:12] The solver can return any one of these. [6:14] Let's narrow this down by adding constraints that specify [6:17] the input to the algorithm. [6:19] To multiply, say, 5 and 3, we first convert those numbers into binary [6:24] and based on that we put additional constraints on the input wires [6:27] that just say that wire x1 is 0, x2 is 1, and so on up to wire x8. [6:33] If we run our SAT solver now with these new constraints, [6:36] only one solution is valid. [6:38] The one that corresponds to running the multiplication circuit on [6:41] the input numbers we specified. [6:43] If we then look at the variables that encode the output wires, we can find the [6:47] value of the product, in this case 15. [6:49] Okay, maybe multiplying numbers using SAT is a bit underwhelming, but [6:53] the real fun starts when we realize we can also do the opposite thing. [6:57] Instead of adding constraints that specify a particular input to the algorithm, [7:01] we can also fix a certain output. [7:04] For example, if we want to force the output of the circuit to be 15, we can [7:08] do it in the exact same way as with the input, We just fixed the values of the [7:12] output wires instead of the input ones. [7:14] And that narrows down the possible solutions to the SAT problem to only [7:18] the ones where the output is 15. [7:20] In other words, we're solving the question: if we know the [7:23] output of the circuit is 15, what does its input have to be? [7:28] That is, we're solving factoring. [7:31] There might be multiple possible inputs leading to the same output, and the SAT [7:34] solver will just choose any one of these. [7:38] For example, in this case, we found that 15 equals... [7:41] 1 times 15. [7:43] Well, that's not very helpful, is it? [7:44] When we're factoring, we also need to specify that both of the [7:47] numbers must be bigger than 1. [7:49] We can ensure that's the case by adding a few extra gates to the circuit. [7:53] It would be a bit too messy to show that here, so here they are in isolation. [7:59] Alright, we run the circuit backwards again, [8:03] and there we go, we've discovered that 15 equals 5 times 3. [8:07] Brilliant. [8:09] And if we try to do the same thing for the number 13, the SAT solver simply tells [8:13] us that our instance is not satisfiable, which is because 13 is a prime number. [8:17] Can we use our trick on larger numbers to break RSA? [8:21] That would require factoring numbers of size about 10^500. [8:26] Using our trick, we would get instances of satisfiability [8:29] with about 50 million variables. [8:32] That's way too much for existing SAT solvers, so we [8:34] didn't break RSA, fortunately. [8:37] But the point is that if we did have a solver that could run in, say, [8:40] linear or quadratic time, we would be able to use it to break RSA. [8:47] So an efficient SAT solver would mean breaking RSA, which is, of course, [8:52] already a massive consequence. [8:53] But if you think about it, the power goes far beyond that. [8:56] If you look back at how we converted factoring to SAT, The only particularity [9:00] of that problem was that you can use a small circuit to multiply two numbers. [9:04] SAT then enabled us to, in a sense, run the multiplication circuit [9:08] backwards and solve factoring. [9:10] Of course, you can't literally run a circuit backwards, that's why the [9:14] satisfiability problem is so hard. [9:17] It's a bit more precise to think of this as inverting functions. [9:20] If you think about the original circuit as computing some function, our trick [9:24] allows us to represent the inverse of that function as a SAT problem. [9:28] If there are multiple inputs leading to the same output like here, our trick [9:32] leaves it to the SAT solver to choose one. [9:35] At this point, it's really important to understand that any algorithm [9:38] can be represented as a circuit. [9:40] We wrote a proof of that in our linked blog post, but if you don't want to [9:44] read it, just look closely at your CPU. [9:46] Ultimately, it's just a bunch of wires and gates. [9:50] So, whenever we have an algorithm, we can think of it as a circuit [9:54] and then use SAT to invert it. [9:56] So, instead of answering the question "if I run the algorithm on a given [10:00] input, what output do I get?", we can encode the question "if I want [10:04] a certain output, what input do I need to feed into the algorithm?" [10:09] This is an incredibly powerful trick, so let's see some more [10:12] examples of how it can be used. [10:14] For example, take the 3-coloring problem where you are given a graph and you're [10:18] supposed to color each node in one of three colors such that every two [10:21] neighboring nodes have different colors. [10:24] So, this would be a valid coloring, but if we change the color of this vertex, [10:28] it's no longer valid because now it shares a color with one of its neighbors. [10:33] When we have a proposed solution, it's easy to check whether it's correct. [10:35] We just iterate over all the edges, and for each one, we make sure that [10:39] the two sides have different colors. [10:41] So again, we can think of this checking algorithm as a circuit. [10:45] Oof, the circuit looks even messier than the multiplication one. [10:49] Let's at least fade some of these wires out so that we can see it better. [10:53] I won't go into the details here, but the basic idea is that we have some [10:56] gates for every node and for every edge, and together, these check that [11:00] the coloring is valid on all edges. [11:03] Then, there's this single output wire coming out of this messy circuit. [11:06] It tells us whether all of the gates output 1, in other words, whether [11:10] the input is a valid coloring or not. [11:13] When we run the circuit on this faulty coloring, we see that the output is 0. [11:18] It's because this NAND gate is not happy about these two vertices that [11:21] are adjacent and have the same color. [11:24] Then, we encode it into a SAT problem and add a constraint [11:27] saying that the output must be 1. [11:29] This way, we've managed to invert the checking algorithm. [11:33] The SAT instance now asks to find a set of inputs that the [11:37] coloring checker will accept. [11:38] In simpler words, we've encoded the problem of solving 3-coloring. [11:43] In general, think of any problem like coloring where you can quickly check [11:47] whether a proposed solution is correct or not, using a verification algorithm. [11:51] We can use our trick to encode the inverse function as a SAT problem. [11:55] But this function maps the output YES to a valid solution. [11:59] This gives us an incredibly general way of solving problems. [12:03] We can now finally connect everything to P versus NP. [12:06] The theoretical definition of a fast algorithm is that its time [12:11] complexity is a polynomial function. [12:13] The class of all problems where you can verify proposed solutions [12:16] in polynomial time is called NP. [12:18] And it contains most important computer science problems, including coloring, [12:23] factoring, and even much simpler ones like multiplying two numbers. [12:27] The trick of converting checking algorithms to SAT [12:30] works in polynomial time. [12:31] This means that a SAT solver that also runs in polynomial time [12:35] would imply a polynomial-time solution for any problem in NP. [12:39] But here's a fun fact: the satisfiability problem itself is in the class NP. [12:45] A problem is in NP if there is a polynomial-time algorithm [12:48] for checking solutions to it. [12:50] And for SAT, checking if a solution is valid is easy. [12:53] You just iterate over all the constraints and verify that all of them are satisfied. [12:58] So you can view satisfiability as the hardest problem in NP. [13:01] Because once you've solved SAT, you've solved everything in this class. [13:06] Formally, we say that a problem is NP-complete if it's both in NP [13:11] and any other NP problem can be reduced to it in polynomial time. [13:15] So using our trick of converting algorithms to SAT, we can prove [13:19] that satisfiability is NP-complete. [13:21] This is one of the most important results of theoretical computer science, [13:25] and it was proven more than 50 years ago by Steve Cook, and independently [13:29] by Leonid Levin, who you may remember from one of our earlier videos. [13:33] And it gets weirder. [13:35] Soon after Cook proved that SAT is NP-complete, another computer scientist [13:39] named Richard Karp published a famous paper in which he basically said, Hey, I [13:43] looked around at about 20 other problems in NP, like the coloring problem or [13:46] the traveling salesman problem, and all of these problems are NP-complete too. [13:51] He proved this using so called reductions. [13:54] Basically, similar to how we converted the factoring problem to satisfiability, [13:58] you can start from SAT and convert it to other problems like graph coloring. [14:02] Soon after Karp, researchers identified thousands and thousands of additional [14:06] NP-complete problems covering all areas of computer science, like graph [14:10] theory, optimization, machine learning, bioinformatics, and even playing games. [14:15] Remember, NP-completeness means that if you have a polynomial algorithm for any [14:19] NP-complete problem, you have one for all other NP-complete problems as well. [14:24] So in some sense, it's debatable whether NP-complete problems are even different. [14:28] They're all just different formulations of a single problem: satisfiability. [14:33] All of this begs the question, is there a polynomial-time [14:37] algorithm for satisfiability? [14:39] This is the famous P versus NP problem. [14:42] At this point in time, the best SAT solvers are, in the worst case, not much [14:46] faster than just trying all possible assignments, which takes exponential time. [14:50] You can solve small instances of SAT using this brute force approach, but [14:54] already in the 60s, researchers pointed out that you can't solve big instances [14:59] of SAT if you just try and try and try. [15:02] And that makes a lot of sense, because this whole video explains how a fast [15:06] algorithm for satisfiability would have so many wild consequences. [15:11] We have this intuition that there is a huge difference [15:14] between verifying a potential solution and solving the problem. [15:17] Equivalently, we think that if there is a fast algorithm implementing some [15:21] function, there doesn't necessarily have to be one for the function's inverse. [15:26] A polynomial-time SAT solver would shatter this intuition, and it would [15:29] mean fast algorithms for literally thousands of NP-complete problems. [15:34] It would also imply that cryptography is impossible. [15:37] That's not just because we would break RSA, as we mentioned. [15:40] Think also of hash functions. [15:42] Such functions are often called one way functions, because they're [15:45] literally designed to be easy to compute, but very difficult to invert. [15:51] You can think of these functions as blenders. [15:53] Will it blend? [15:55] That is the question. [15:59] They perform complicated operations on the input bits, making it difficult to [16:03] reverse them if you only have the output. [16:05] It's analogous to the notion of entropy and the second law of thermodynamics. [16:09] It seems that it's easier to make a mess than put the pieces back together. [16:13] Unfortunately, the difference between physics and computer science is that we [16:17] can't simply declare P does not equal NP as a law of nature and claim our Nobel prize. [16:23] As far as we know, fast SAT solvers could be mathematically possible, and so we [16:27] maybe could invert any messy algorithm. [16:30] We just think it's very unlikely. [16:32] But in that case, why don't we have a mathematical proof [16:35] that P does not equal to NP? [16:37] The big issue here is that while we have a lot of tricks for coming up [16:40] with fancy new algorithms to solve problems, we don't really have good [16:44] ways of proving that a certain problem can't be solved with a fast algorithm. [16:48] So we suspect that P does not equal to NP, but also that [16:52] proving it is really, really hard. [16:54] I think this is a good intuition for what the P versus NP problem is really about. [16:58] The heart of the problem is whether we can invert algorithms. [17:02] This is of course closely connected to the standard way of framing the question, [17:06] namely whether we can efficiently solve problems if we're able to [17:09] efficiently verify proposed solutions. [17:12] That's because inverting a checking algorithm enables us [17:15] to solve the original problem. [17:17] I hope you find this intuition helpful too. [17:19] If you have a question, just leave us a comment. [17:21] Also, check out our blog post where we correct some of the inaccuracies [17:25] that we made here for the sense of clarity, and we also explain some [17:28] things that we considered too crazy even for our polylog standards. [17:32] That includes how you can explain the success of deep learning by viewing [17:36] backpropagation as an algorithm that can kind of invert circuits. [17:40] If you enjoy our videos, please like and subscribe. [17:43] Ah, that's so cheesy, isn't it? [17:45] If you enjoy our videos, like and subscribe, and consider [17:49] supporting us on Patreon. [17:50] I'll see you next time.