> [NP means that] a non deterministic machine (one that could magically search multiple states at once) can find a solution in polynomial time Which is exactly

> [NP means that] a non deterministic machine (one that could magically search multiple states at once) can find a solution in polynomial time Which is exactly what quantum computers can do for certain classes of problems, such as integer factorization. Sadly, it seems not to be the case (or not yet found?) for the most well known and useful class of NP problems, NP-complete. See this discussion https://news.ycombinator.com/item?id=1371150 https://news.ycombinator.com/item?id=1371150