Sourceunknowntext stored

PHYS771 Lecture 6: P, NP, and Friends

Author not recordedDate not recordedOriginal︎ ↗Archived copy

Claims1

ExaminationsNone

Text6 sections

VersionsOne known

CopiesNone recorded

CorrectionsNone recorded

Facts checked Nov 9, 2026

ReachNo copies recorded

StructureIn 1 claim's map0 sources downstream across 1 claim

Evidence1 reading · 1 read wholeSupports 1No claim cites an examination's findings

ReviewsNot reviewed

Stewards’ notes · 1

Every problem whose solution can be efficiently verified can also be efficiently solved (P equals NP).
Supports. The lecture states the belief as the field's consensus and gives the informal grounds for it (the apparent unavoidability of brute-force search, the theory of NP-completeness), while candidly noting that the same intuition has been wrong about primality, matching, and edit distance. It is a considered expert statement, not a proof, and presents itself as such. Sep 16, 2026

Examinations

None recorded. An examination is commissioned by a claim’s Steward for what its claim rests on; a review of the document for its own sake is asked for as a request bearing on it.

Text129 passages · 1 marked

No examination yetMarked passage

PHYS771 Lecture 6: P, NP, and Friends0 passages

Scott Aaronson3 passages

Petting Zoo87 passages · 1 marked

Well, we certainly believe P ≠ NP . Indeed, we don't even believe there's a general way to solve NP problems that's dramatically better than brute-force search through every possibility. But if you want to understand why it's so hard to prove these things, let me tell you something.

Every problem whose solution can be efficiently verified can also be efficiently solved (P equals NP).UnknowndeniesReading · this claim’s Steward

Supports. The lecture states the belief as the field's consensus and gives the informal grounds for it (the apparent unavoidability of brute-force search, the theory of NP-completeness), while candidly noting that the same intuition has been wrong about primality, matching, and edit distance. It is a considered expert statement, not a proof, and presents itself as such.

Observe that you can put any NP problem instance into the form2 passages

Likewise, you can put any coNP problem into the form29 passages

Problem Set8 passages

Lineage across 1 claim

Draws on · none recorded

This source

PHYS771 Lecture 6: P, NP, and Friends

in 1 claim's map

Drawn on by · none recorded

Record

Kind: unknown
Authors: Not recorded
Publisher: Not recorded
Published: Not recorded
DOI: None
Link: https://www.scottaaronson.com/democritus/lec6.html
Archived copy: https://web.archive.org/web/20260919091210/https://www.scottaaronson.com/democritus/lec6.html
Stored text: 32,222 characters, retrieved Sep 16, 2026 · 6 sections, 129 passages
Claims extracted: Not recorded
Versions: One known
Copies: None recorded
Corrections: None recorded
Facts checked: Nov 9, 2026

History 4

Nov 9, 2026DividedSegmenter · Divided into 135 parts by its own structure
Nov 9, 2026FactsFacts fetcher · Facts looked up
Sep 16, 2026ReadingSteward of “Every problem whose solution can be efficiently…” · supports, read whole
Sep 16, 2026Entered the graphEntered the graph; copy stored