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

The original Church-Turing thesis says nothing about computational complexity. Extended Church-Turing thesis says that all Turing machine equivalent computers can compute the same problems withing polynomial time.

Quantum computers are not known to be capable of solving NP-Complete problems in polynomial time.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

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

Search: