Comment

Comment by yifanlu

From Scott Aaronson

> Yet another reason to be excited about this result—one that somehow hadn’t occurred to me—is that, as far as I know, it’s the first-ever fully convincing example of a non-relativizing computability result.

This is one of the three known barriers any proof of P vs NP must overcome. Not saying any of this applies to P vs NP but the proof technique demonstrated is important for such a proof.

parent yifanlu 6 years ago

No comments yet

Be the first to share your thoughts.

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton