vasekrozhon

Hi, the author here.

@JoshCole Thanks -- I also like that lecture by Ilya, added it to the resources now.

@0ffh -- Yeah I hope the page does not come across as me trying to claim some new revolutionary insights. People like Ilya have been talking about this years ago - I am just trying to package it into a hopefully more accessible format.

Hi, the author here. It was meant as a light joke, and I totally agree that we should not feel bad if an AI can predict the next letter better than us. Maybe I should rephrase it to something like "IQ test for AIs" to hint a bit more about what's to come -- this is what we train the AIs for to be intelligent.

Hi, a few commenters on Youtube also asked us this question. I just now added the last section to the blog post that discusses it. Basically, although we only show how to find one arbitrary solution, you can use this trick to also find all of them efficiently in terms of the size of the input and the number of solutions.

Exactly! In theoretical computer science, we have a lot of experience coming up with new algorithms but no idea how to prove lower bounds. So I would say that new lower-bound technique is perhaps the most interesting thing we would learn from the proof of P!=NP.

But, of course, P vs NP is clearly central to computer science and math for a bunch of other reasons, hopefully, our video provided some intuitions.

Hi, the author of the blog post here.

The section was written horribly -- while I was talking about backpropagation, I was thinking about "what can be done in polynomial time" and there's a mismatch as you explained. Thanks and shame on me, I rewrote it.

In any case, I would recommend watching the video first, the article is just accompanied stream of consciousness for those few who really liked the video.

Hi, the author of the blog post here.

1) With others, I work on high-effort Youtube videos, our channel's called Polylog. We recently made a video about an underrated take on P vs NP. [1]

2) After working on the high-effort video, I always write a low-effort stream-of-consiousness-style very-much-unedited blog post where I clarify some details or explain some more esoteric stuff that did not make it into the video. The blog post you are discussing is such a blog post. So you should watch the video first and read the blog post only if you really liked the video and want to know more. :)

3) If you have any questions, I'll be happy to answer them!

[1] https://www.youtube.com/watch?v=6OPsH8PK7xM

> I guess pretty much for the same reason P is probably not equal to NP.

Yep, in particular there are classes called #P and PP that are closely connected to NP that can capture the hardness of problems like computing partition functions, sampling from posterior distribution and so on.

This is just me being bad at English. I now rewrote the first paragraph of the blog post to hopefully make it clear that I am just claiming that our nonstandard way of viewing P vs NP is underrated, not the problem itself. :)

Yes! We are not trying to claim that P vs NP is underrated in the video, just the bit with interpreting it as a question about inverting functions. I think using "underrated" is justified, I talked with a bunch of people about this topic and it was a new way of looking at it for a lot of them.

Of course, using the title "What P vs NP is actually about" is a bit of a stretch -- "Interesting take on P vs NP" would be more honest.

Thanks. I also added the link to the post now. Frankly, I did not count on people getting to the blog post in any other way than being curious after watching the video. :D

Sorry, I added the credit now. Hope you don't mind it now? :)

I have to say that I find these pictures extremely aesthetical. It's crazy how the brutally powerful CPUs we have today are successors to processors created not so long ago that also, though very intricate, fit into one picture...