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

Surprisingly, this cannot be the case, not without discovering a completely new kind of independence proof. [0] p26 discusses the problem.

> At the end of the day, a polynomial-time algorithm for 3-SAT either exists or it doesn't!

[0] https://www.scottaaronson.com/papers/pnp.pdf



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

Search: