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

No, we know that P != EXP_TIME, by the time hierarchy theorem - i.e. we know some problems (and we do have concrete examples) take exponential time. What we don't know is that there exists a problem that requires exponential time (or otherwise greater than polynomial) where we can create a proof that a answer is correct which is checkable in polynomial time.

https://en.wikipedia.org/wiki/Time_hierarchy_theorem



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

Search: