|
|
|
|
|
|
by MrMoenty
3046 days ago
|
|
|
Well, funnily enough, quantum computing CAN help with factoring, and likely not with TSP. Factoring is one of those rare problems in NP that is not known to be NP-complete, but for which we also don't know a polynomial algorithm. In 1994, Peter Shor came up with a quantum algorithm that solves factoring in polynomial time [1]. On the other hand, it is generally not believed that quantum computers would be able to solve NP-complete problems such as TSP in polynomial time. [1] https://en.wikipedia.org/wiki/Shor%27s_algorithm |
|
|