Hacker News new | past | comments | ask | show | jobs | submit login

Just a half minute skim shows the author claims it passes the natural proof barrier but makes no claim about it being non-relativizing or non-algebraizing.



For those following along at home: this is important because we have a proof that relativizing wouldn't work. In this context, relativizing means relative to an oracle. For example, P^A means "just like a Turing machine would regularly recognize languages except this one has a magical oracle that can recognize A in one step". A can be arbitrarily complex, including NP-complete ones like 3SAT.

This is important because the Baker-Gill-Solovay theorem already demonstrates that there exist oracles A != B relative to which P^A = NP^A, but P^B != NP^B. This shows that the problem has contradictory relativizations, and hence can't be proven that way. This matters because it's a litmus test against quack proofs.

I don't think this is a problem here; the proof doesn't appear to be doing that.


I first learned about this because there's a decades-old joke in NetHack that cites this result when you ask for a major consultation from the Oracle when you can't afford to pay for it. I think the joke is that in this case, the Oracle can't tell you anything that's useful to you. :-)


AFAIK boolean circuits proofs generally don't relativize, so there's no need to discuss that.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: