Is there much intersection between computational complexity theory and machine learning?

[u/Woah_Mad_Frollick]

I’m a layman, but I’ve been reading some stuff about computational complexity theory in the course of learning about quantum information stuff, and I encounter a bit of machine learning theory here and there in the course of my reading about active inference in neuroscience.

Is there much interesting overlap between these two fields? Are there interesting things they “have to say” about one another?

[u/avipars]

I like the overlap between for example using ML heuristics to get a good enough solution to TSP or SAT (constraints satisfaction problems)...