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

No, he is claiming that l-CLIQUE requires exponential circuit size (this is the reason that most of the proof talks about circuit complexity and not time bounded Turing Machines). This is not necessarily the same thing as exponential time.


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

Search: