Skip to main content
NP-completeness

NP-completeness

Search complete. 9 mentions across 6 episodes found for "NP-completeness".

Nov 20, 2026

Ryan PetersonGUEST
12:46
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.
Ryan PetersonGUEST
12:59
This reduces from solving the multiple choice knapsack problem, which we know to be NP-complete.
Ryan PetersonGUEST
13:05
However, we've come up with a fast, efficient approximation algorithm for this optimization that runs in time MD log MD.
Ryan PetersonGUEST
13:15
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.
Kiran VodrahalliGUEST
19:24
So first, you know, we have to figure out what we should even try to shoot for.
Kiran VodrahalliGUEST
19:29
So it turns out that what is possible to attain a certain profit is NP-complete, a reduction from partition.
Kiran VodrahalliGUEST
19:36
So our goal is just an approximate algorithm in polynomial time.
Kiran VodrahalliGUEST
19:43
So we can come up with the following dynamic program for the FPTAS.

14 MINS LATER

Kiran VodrahalliGUEST
34:06
So I'm going to summarize.
Kiran VodrahalliGUEST
34:12
So platform design, the point was to model the economic activity of online firms.
Kiran VodrahalliGUEST
34:18
The general case of platform design is strongly NP-complete, hard to approximate, but there is a tractable special case called the Flower MDP.
Kiran VodrahalliGUEST
34:28
has a greedy algorithm.
Yann LeCunGUEST
38:39
Not immediately realizing that most of the problems that you need to solve, almost all of them are intractable.
Yann LeCunGUEST
38:48
NP-complete, NP-hard, or whatever, right? And so they started relying on heuristics and blah, blah, blah.
Yann LeCunGUEST
38:55
And that led to sort of the classical Google fashion AI kind of branch, if you want.
Yann LeCunGUEST
39:01
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.
Mikhail BrudnoGUEST
30:19
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.
Mikhail BrudnoGUEST
30:32
If edges had distances and they were written in binary, it would be NP-complete.
Mikhail BrudnoGUEST
30:36
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.
Mikhail BrudnoGUEST
30:48
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...
Mikhail BrudnoGUEST
30:58
That's a open problem.
Mikhail BrudnoGUEST
31:00
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.
Mikhail BrudnoGUEST
31:13
Well, no, what they mean is not genome assembly is NP-complete, but the X model of genome assembly is NP-complete.
Mikhail BrudnoGUEST
31:19
Genome assembly is not a theoretical problem.
Kevin O'NeillHOST
8:46
cost some companies tens and even hundreds of millions of dollars.
Karl DenningerGUEST
8:50
And the basic issue there is that a machine can and does write what could be called NP-complete code.
Karl DenningerGUEST
9:05
software in that it will compile.
Karl DenningerGUEST
9:07
It doesn't have syntax errors in it because the machine has all of the syntactical rules.
Type 3 AudioNARRATOR
52:03
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.
Type 3 AudioNARRATOR
52:18
In particular, many practical problems turn out to be NP-complete, which makes NP a natural complexity class to focus on.
Type 3 AudioNARRATOR
52:26
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.
Type 3 AudioNARRATOR
52:41
Decisions about what to work on can be conceptual or non-conceptual.

We value your privacy

We use cookies to understand how you use our platform and to improve your experience. Click “Accept All” to consent, or “Decline non-essential” to opt out of non-essential cookies. Read our Privacy Policy.