
NP-completeness
9
MENTIONS
6
EPISODES
4
PODCASTS
Search complete. 9 mentions across 6 episodes found for "NP-completeness".
Nov 20, 2026
Near-optimal Monitoring of Online Data Sources
R
12:46Ryan PetersonGUEST
But I do want to give a high level description by saying that once we have this general optimization problem We recognize that it's NP-hard because we need to choose an integral value for each of the levels in the system.
R
12:59Ryan PetersonGUEST
This reduces from solving the multiple choice knapsack problem, which we know to be NP-complete.
R
13:05Ryan PetersonGUEST
However, we've come up with a fast, efficient approximation algorithm for this optimization that runs in time MD log MD.
R
13:15Ryan PetersonGUEST
We do this by taking our optimization problem and transforming it using Lagrange multipliers into a single expression that needs to either be maximized or minimized.
The Platform Design Problem
K
19:24Kiran VodrahalliGUEST
So first, you know, we have to figure out what we should even try to shoot for.
K
19:29Kiran VodrahalliGUEST
So it turns out that what is possible to attain a certain profit is NP-complete, a reduction from partition.
K
19:36Kiran VodrahalliGUEST
So our goal is just an approximate algorithm in polynomial time.
K
19:43Kiran VodrahalliGUEST
So we can come up with the following dynamic program for the FPTAS.
14 MINS LATER
K
34:06Kiran VodrahalliGUEST
So I'm going to summarize.
K
34:12Kiran VodrahalliGUEST
So platform design, the point was to model the economic activity of online firms.
K
34:18Kiran VodrahalliGUEST
The general case of platform design is strongly NP-complete, hard to approximate, but there is a tractable special case called the Flower MDP.
K
34:28Kiran VodrahalliGUEST
has a greedy algorithm.
Masterclass Edition: Yann LeCun on AMI Labs and the Path Beyond LLMs
Y
38:39Yann LeCunGUEST
Not immediately realizing that most of the problems that you need to solve, almost all of them are intractable.
Y
38:48Yann LeCunGUEST
NP-complete, NP-hard, or whatever, right? And so they started relying on heuristics and blah, blah, blah.
Y
38:55Yann LeCunGUEST
And that led to sort of the classical Google fashion AI kind of branch, if you want.
Y
39:01Yann LeCunGUEST
And then simultaneously, you know, also in the 50s, there were people who were trying to do neural nets at the time, and, you know, they didn't go very far, and they kind of died in the late 60s and reappeared only in the 1980s with backprop with multilayer neural nets.
Genome Assemby, Chinese Postman, and Virtual Clusters
M
30:19Mikhail BrudnoGUEST
Is there a Chinese tour of a particular length? So that is a problem that's difficult because you can think of the numbers as written in unary because every edge has length exactly one.
M
30:32Mikhail BrudnoGUEST
If edges had distances and they were written in binary, it would be NP-complete.
M
30:36Mikhail BrudnoGUEST
Another open problem, is there a Chinese super work that uses every edge a given number of times? So we said earlier that if every edge is used once, the problem is polynomial time.
M
30:48Mikhail BrudnoGUEST
Well, what if God came down and told us you have to use this edge 25 times and this edge 17 times? Is there then a Chinese postman tour? So...
M
30:58Mikhail BrudnoGUEST
That's a open problem.
M
31:00Mikhail BrudnoGUEST
And one problem which remains open, is there a polynomial time model for genome assembly? And that's sort of still quite open because, so usually people say, genome assembly is NP-complete.
M
31:13Mikhail BrudnoGUEST
Well, no, what they mean is not genome assembly is NP-complete, but the X model of genome assembly is NP-complete.
M
31:19Mikhail BrudnoGUEST
Genome assembly is not a theoretical problem.
If We Knew What Broke It
K
8:46Kevin O'NeillHOST
cost some companies tens and even hundreds of millions of dollars.
K
8:50Karl DenningerGUEST
And the basic issue there is that a machine can and does write what could be called NP-complete code.
K
9:05Karl DenningerGUEST
software in that it will compile.
K
9:07Karl DenningerGUEST
It doesn't have syntax errors in it because the machine has all of the syntactical rules.
“A basic case for accelerating conceptual reasoning capabilities” by Emery Cooper, Caspar Oesterheld, Chi Nguyen
T
52:03Type 3 AudioNARRATOR
Similarly, the foundational concepts of computational complexity theory, for example, worst-case Big O analysis and the classes P and NP, can be viewed as conceptually natural, but their centrality stems mostly from practical considerations.
T
52:18Type 3 AudioNARRATOR
In particular, many practical problems turn out to be NP-complete, which makes NP a natural complexity class to focus on.
T
52:26Type 3 AudioNARRATOR
And although people probably care more about exact runtimes than about worst-case Big O complexity for applications, exact runtime bounds are extremely hard to derive theoretically, whereas Big O analysis is far more tractable while still being informative enough in practice.
T
52:41Type 3 AudioNARRATOR
Decisions about what to work on can be conceptual or non-conceptual.