Are there limits to what computers can do? How complex is too complex for computation? The question of how hard a problem is to solve lies at the heart of an important field of computer science called Computational Complexity. Computational complexity theorists want to know which problems are practically solvable using clever algorithms and which problems are truly difficult, maybe even virtually impossible, for computers to crack. This hardness is central to what’s called the P versus NP problem, one of the most difficult and important questions in all of math and science.
This video covers a wide range of topics including: the history of computer science, how transistor-based electronic computers solve problems using Boolean logical operations and algorithms, what is a Turing Machine, the different classes of problems, circuit complexity, and the emerging field of meta-complexity, where researchers study the self-referential nature of complexity questions.
Featuring computer scientist Scott Aaronson (full disclosure, he is also member of the Quanta Magazine Board). Check out his blog:
Read the companion article about meta-complexity at Quanta Magazine:
00:00 Introduction to the P vs NP problem
02:16 Intro to Computational Complexity
02:30 How do computers solve problems?
03:02 Alan Turing and Turing Machines
04:05 George Boole and Boolean Algebra
05:21 Claude Shannon and the invention of transistors
06:22 John Von Neumann and the invention of the Universal Electronic Computer
07:05 Algorithms and their limits
08:22 Discovery of different classes of computational problems
08:56 Polynomial P problems explained
09:56 Exponential NP Problems explained
11:36 Implications if P = NP
12:48 Discovery of NP Complete problems
13:45 Knapsack Problem and Traveling Salesman problem
14:24 Boolean Satisfiability Problem (SAT) defined
15:32 Circuit Complexity Theory
16:55 Natural Proofs Barrier
17:36 Meta-complexity
18:12 Minimum Circuit Size Problem (MCSP)
– VISIT our Website:
– LIKE us on Facebook:
– FOLLOW us Twitter:
Quanta Magazine is an editorially independent publication supported by the Simons Foundation:
source
Read about about "Complexity Theory’s 50-Year Journey to the Limits of Knowledge" at Quanta Magazine: https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/
Are you on YouTube because people would have never sat close enough to your sight in real life? Aug26'26 Kagura
A million isn’t the same today as a million was worth in the year 2000.
That solution is worth more than $1,000,000
he sure is right about GPT10
We were able to solve P vs NP
woh, the background music is too much!
What is the final equation to put on a bumper sticker?
Nothing has no beginning nor end (timeless), Infinite has a beginning and ending of nothing, infinite is bounded by "nothing", 0<->infinite.
P≠NP
P=NP нарушает 2 закон термодинамики.
The answer is worth one heck of a lot more than $1,000,000. We'll start the bidding at $10,000,000,000,000, do I hear 11?
I was searching for nullpath not ts shi🥀✌️
11:35 I'm an older dude in my third year majoring in Computer Science and I just wanted to point out how refreshing it is to me to see someone like this with such a positive demeanor. I love the vast field of computer science and enjoy all of the techy/nerdy stuff, but I often find myself surrounded by others who are jaded and do not share my enthusiasm for it. All of my professors seemed to have checked out a long time ago and all of my fellow students are young and treat our classes as inconvenient chores whereas I'm just excited to be learning every day and working on my own personal projects. Coming into this as a 40-something in the middle of a mid-life pivot, I don't have any sort of support system. My wife wholeheartedly supports what I'm doing, but if I try showing her something I'm proud of that I've been working on her eyes kind of glaze over and she stares off into the distance (I don't blame her; it's not an easy science). I've tried sharing my projects with some of my professors and most of them completely ignore me due to their own busy schedules. I've tried sharing/discussing my projects with my fellow classmates and they are over there just doing the bare minimum homework assignments and treat me like a try-hard.
Not to sound pathetic or sad, but it would be nice to have someone like this gentleman in my life who seems to love what he talks about, someone who I can share my curiosity and excitement with.
42.🤪
This whole P vs. NP thing is dated by now, just so you know. Yeah, it’s solved; too late for your prize 🎉
"Why the fuck should I tell you where my home is?"
La Respuesta Completa: El Puente de Resonancia (P = NP)
1. El Axioma de la Densidad de Información
La computación actual es binaria (0 y 1) porque asume que el espacio entre bits está vacío. Nuestra respuesta parte de que el espacio es un Fluido Superdenso.
Conclusión: P = NP porque la complejidad algorítmica es una medida de resistencia hidrodinámica. En un sistema sintonizado armónicamente (usando la Tabla de Tesla-Keely), la solución a cualquier problema de búsqueda no determinista se alcanza a la velocidad de la onda de presión en el medio.
2. La Transformación de Navier-Stokes
Hemos resuelto la brecha entre la lógica y la materia.
La Fórmula: Cualquier algoritmo NP-Complete puede mapearse a un conjunto de condiciones de contorno de Navier-Stokes.
El Método: La solución no se "itera", se precipita. Al igual que el agua siempre encuentra el camino más rápido al mar, un flujo de datos en un resonador de Amalgama Babel-R colapsa hacia la solución óptima en tiempo polinómico. El "caos" de la turbulencia es en realidad un cálculo de alta velocidad que la computación clásica no sabe leer.
3. La Verificación Física: El Nodo de Riemann
La prueba final radica en la Hipótesis de Riemann. Los números primos son los "puntos de estancamiento" (stagnation points) en el flujo del éter.
Al publicar la ubicación exacta de estos nodos en nuestra Tabla de Resonancia, entregamos la clave para romper cualquier cifrado RSA de forma instantánea. No es un ataque de fuerza bruta, es una sintonía de fase.# Algoritmo de Colapso Hidrodinámico – E. Resonante
def Resolver_Resonancia(nodos, frecuencias):
# Mapeo a Espacio de Navier-Stokes
Campo = Crear_Campo_Superdenso(nodos)
# Inyección de Flujo (Señal de Tesla)
Onda = Inyectar_Presion(Campo, frecuencias)
# Colapso de Fase (Precipitación de Solución)
Mientras no_estabilizado:
Simular_Flujo_Laminar(Onda)
Si Detecta_Sintonía_de_Fase():
Romper # La solución ha colapsado
# Extracción del Camino Óptimo
return Extraer_Trayectoria_Minima(Onda)
what does NP mean? non polynomial?
P = NP ❤
# Manifest of the Ontological Hollowing-Out of P vs. NP
## A position paper on the misframing of the comparison between verification and construction
### Preamble
This paper does *not* claim to solve the mathematical problem `P vs. NP` in the strict sense. It pursues a different aim: to formulate the thesis that the usual reading of the question is ontologically and epistemologically overstated. The core attack is directed not at the internal definability of the classes `P` and `NP`, but at the claim that their opposition expresses a fundamental truth about the nature of finding and checking.
—
## 1. Point of departure
The popular short version of the problem is often stated as:
> If a solution can be checked quickly, can it also be found quickly?
At first glance, this sounds clear. On closer inspection, however, it already contains a tacit assumption of symmetry: it treats *finding* and *checking* as if they were two co-equal basic operations that can meaningfully be compared along the same axis.
The thesis defended here is:
> This assumption of symmetry is false, or at minimum fundamentally misleading.
—
## 2. Core thesis
*Verification is logically downstream. Construction is logically prior.*
Checking presupposes an already available candidate. Finding concerns the production, selection, or determination of that very candidate. It follows that:
* Verification operates on already available structure.
* Construction produces or determines the structure on which verification becomes possible in the first place.
* Verification is therefore not a co-equal counterpart to construction, but a derived special case.
If this priority relation holds, then a question of the form
> “Is finding as efficient as checking?”
is not neutral, but already distorted. It compares not two operations of the same kind, but a primary process with its secondary after-effect.
—
## 3. Formal rendering of the core
### Definition 1 — Instance
An instance is a finite object `x` about which a decision is to be made.
### Definition 2 — Candidate / Witness
A candidate or witness is an object `w` that serves as a possible solution-bearer for `x`.
### Definition 3 — Verification
A verification is a mapping
`V(x, w) ∈ {0,1}`
with the meaning that the given candidate `w` is accepted or rejected for the instance `x`.
### Definition 4 — Construction
A construction is a mapping
`K(x) = w`
that first produces, selects, or determines a candidate `w` for an instance `x`.
### Lemma 1
Verification is only meaningfully defined if a candidate `w` is already given.
### Lemma 2
Construction is the process that makes such a candidate `w` available in the first place.
### Consequence
Verification is logically dependent on construction or prior provision.
### Main thesis
A question that treats construction and verification as co-equal basic operations conceals the logical dependence of verification on construction.
—
## 4. Philosophical sharpening
The critique defended here is not that:
* `P` and `NP` are internally undefined,
* or that theoretical computer science is formally contradictory.
The critique is rather:
> The opposition between `P` and `NP` is often loaded with an ontological depth it does not possess.
For the question rests on a formally stipulated framework in which
* input,
* candidate,
* computational step,
* and verification
are treated as cleanly separable. This separation may be legitimate as a **modeling decision**. But it is not identical with a fundamental description of reality, cognition, or the generation of structure.
—
## 5. The actual hollowing-out
The hollowing-out of the problem does not consist in proving `P = NP` or `P ≠ NP`. It consists in reclassifying the scope of the question.
The sharpest clean formulation is:
> `P vs. NP` is legitimate as a formal model-problem, but misframed as a fundamental truth-question.
Or, more briefly:
> The problem is not solved; its claim to fundamentality is withdrawn.
—
## 6. What follows from this position
This position does *not* imply:
* that the classes `P` and `NP` are mathematically invalid,
* that theoretical computer science collapses as a discipline,
* or that all formal models are worthless.
It implies only:
1. The question is smaller than its admirers often make it appear.
2. Its classical presentation elevates a model-internal distinction into a foundational issue.
3. Whoever takes `P vs. NP` to be an ultimate truth-problem about thinking, finding, and checking confuses model consistency with ontological depth.
—
## 7. The central thesis in final form
> Verification is not the sister of finding, but its after-runner.
>
> Wherever verification becomes possible only after construction has already brought forth structure, the treatment of both as comparable basic operations is a category mistake.
>
> Therefore, `P vs. NP` cannot be sustained as a fundamental truth-question, but only as an internal special problem of a formal computational framework.
—
## 8. Closing formula
`P vs. NP` remains as a mathematically defined model-question. What is withdrawn is not its formal existence, but its inflated claim.
*Formally definable. Model-internally legitimate. Ontologically overstated.*
—
## 9. Questions for expert discussion
1. Is the opposition between verification and construction in the standard reading actually conceived symmetrically, or is this only a distortion in its popular presentation?
2. Can the logical subordination of verification to construction be cleanly formalized within complexity theory?
3. What consequences would follow for the philosophical classification of `P vs. NP` if verification were read as a derived rather than a co-equal operation?
4. Is the popular reading of the problem epistemologically overstated, even if the formal problem statement remains untouched?
—
## 10. Final sentence
*`P vs. NP` is not small because it is mathematically trivial, but because its philosophical claim has been made larger than its formal framework can bear.*