Avi Wigderson

This is Avi Wigderson, Turing Award and Abel Prize winner, and I interviewed him all about his field.

In one of your lectures, you mentioned that P equals NP is philosophically about the fundamental limits of human knowledge.

What is P equals NP, and how does it relate to human knowledge?

So I know this is one of those Millennium Prize problems.

There's a million dollar prize if you can provide a proof for this.

I can imagine you could prove that they're equivalent.

You could also prove that they're not.

If you had to guess when and if a proof comes, which direction would your intuition say it goes and why?

That would change the world.

In software engineering, we use algorithms all the time and they often have these very satisfying properties where the solution, you know, we use space or some algorithm that can take something where the brute force is something much larger to down to something that's polynomial time or something very reasonable.

But in all these NP problems, it's pretty unsatisfying that the best we could do is brute force.

Am I understanding that correctly?

You mentioned the protein folding.

And I mean, yeah, that's an interesting one because it's an NP problem, but it was solved to an acceptable extent.

And when I was reading about it, it wasn't solved for 100% of cases.

It provides the solution and a confidence score, but it doesn't give you the answer 100% accurate, fully computed.

And so when you think about these NP problems, what if you relaxed the criteria of being correct?

Could the asymptotic complexity be less than the exponential that we're talking about?

So even if you solve just the slightest epsilon for any trivially small epsilon, it's just as hard as doing the full.

It's just as hard as finding the optimum solution.