Skip to main content
NP-hardness

NP-hardness

Search complete. 17 mentions across 11 episodes found for "NP-hardness".

Nov 19, 2026

Mehdi SharifzadehGUEST
44:19
Give me the one with the sequence that gives the optimal route.
Mehdi SharifzadehGUEST
44:22
And that's actually NP-hard.
Mehdi SharifzadehGUEST
44:24
So, they provided approximation solutions and other queries like k-stop queries.
Mehdi SharifzadehGUEST
44:33
Now, let's say how I'm using, I'm using Warren Diagram to solve this.
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.
Washington TaylorGUEST
50:51
It's really hard to compute those things.
Washington TaylorGUEST
50:52
We don't even have mathematically the formalism to do it, but even if we could, there was a nice argument by Dennef and Douglas which shows that even in the simple models, the problem of finding a vacuum with a small lambda, even given some simple models for how to compute it, is an NP-hard problem.
Washington TaylorGUEST
51:08
It's a lot like the minimal length vector problem.
Washington TaylorGUEST
51:10
You know, this problem where if you're given vector, you're given a set of vectors in a space and the question is, what's the integral linear combination of those vectors of the shortest length?
Washington TaylorGUEST
51:18
That's an NP-hard problem.
Washington TaylorGUEST
51:19
And that is at least the cosmological constant problem, even in the very simplest cartoon characterization is at least that hard.
Washington TaylorGUEST
51:27
So, even if somebody could write down all the models and then ask you to calculate the cosmological constants, it would be very hard to locate our vacuum with 10 to the minus 120 cosmological constant.
Donald KnuthGUEST
80:50
Um, Yeah.
Donald KnuthGUEST
80:52
Um, but- but, uh, uh, there- there- there's, you know, the fast ways to color chordal graphs, there's fast ways to certify independent sets in chordal graphs, and, uh, almost every problem, you know, that's- that- that's NP-hard on general graphs, so they- has a- some kind of efficient algorithm on chordal graphs, and- and on trees usually, but not- not always, but.
Donald KnuthGUEST
81:18
So, yeah.
speaker_8UNKNOWN
81:19
The definition of portal graphs is around the number three.
Zongrui ZouGUEST
5:57
And as you can see, when k is 2, it is just the equivalent to find the mean s, t parts.
Zongrui ZouGUEST
6:03
And when k is at least 3, finding motorway cut becomes NP-hard.
Zongrui ZouGUEST
6:09
And another highly related definition is a global k-card.
Zongrui ZouGUEST
6:12
Again, given a beta graph, we would like to remove minimal edge base to separate the graph into whatever k-connected components.
Justin DomkeGUEST
7:24
It's not going to work.
Justin DomkeGUEST
7:26
And in fact, not only is dynamic programming hopeless, but the problem in general is NP-hard and it's NP-hard even to compute the marginals within some constant factor.
Justin DomkeGUEST
7:33
So, in general graphs, marginalization is a very tough problem.
Justin DomkeGUEST
7:38
But let's return to doing marginals on tractable graphs.
Laurent MassouliéGUEST
6:53
Uh, and since we can square this term, which is, uh, uh, zero-one valued without changing the objective, you can, uh, rephrase it as trying to find a, a permutation matrix that maximizes the trace of the product of, uh, the adjacency matrix A1 of the first graph times permutation matrix pi times, uh, adjacency matrix A2 of the second graph times the transpose of pi.
Laurent MassouliéGUEST
7:18
And, uh, well, this problem is the well-known, uh, quadratic assignment problem, and it is known to be NP-hard, so this is computationally difficult in general.
Laurent MassouliéGUEST
7:27
So, uh, let me, uh, go very quickly over the applications of that problem because this is ICM, and so we don't need to spend too much time on that.
Laurent MassouliéGUEST
7:36
But there are many applications, let's, uh, let's say.
Mrdjan JankovicGUEST
4:50
So, alternatives.
Mrdjan JankovicGUEST
4:53
You can see everything is NP-hard, all the other options, NP-hard, meaning essentially really difficult.
Mrdjan JankovicGUEST
5:01
Discrete search is officially exponential, but whenever it says NP, you can say it's pretty much exponential.
Mrdjan JankovicGUEST
5:08
Now, I can't talk... too much about this.
ChrisHOST
43:17
Right.
ChrisHOST
43:18
Which some would call NP-hard, which is a set of problems that are at least as hard as NP.
ChrisHOST
43:25
We can go into what that means later if we still care.
ChrisHOST
43:29
But anyway, 3SAT is one of these problems.
Chris RéHOST
13:15
Yeah.
Chris RéHOST
13:15
But the other function, just like K-means, was, you know, NP-hard, if you remember last time, but also was a hard function to solve exactly.
Chris RéHOST
13:22
So, you know, the underlying function, you know, it's going to be an approximation in the sense that, you know, we hope to get a good solution out of this.
Chris RéHOST
13:30
We may not have any guarantees.

1 more episode mentions NP-hardness.

Create an account to see the whole feed, search across every transcript, and follow the entities you care about.

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.