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

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.



Applications are open for YC Summer 2018

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

Search: