*It has been shown that if P != NP, then GI is in that valley.* Could you point ... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

bdhe on Oct 8, 2011 | parent | context | favorite | on: An Annoying Open Problem

It has been shown that if P != NP, then GI is in that valley.

Could you point to a reference? Is this true even if P != NP, but NP = coNP?

thesteamboat on Oct 9, 2011 [–]

This pdf (http://www.cs.princeton.edu/theory/complexity/ipchap.pdf) which is a draft chapter from a book by Arora and Barak, shows that if GI is NP-complete, then the polynomial hierarchy collapses to the second level. Collapse to the first level is when NP=coNP. So this is slightly weaker even than that.

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