4 ms·
> And even these algorithms can help asymptotic complexity Is this a theorem or conjecture?
by taejo 9y ago
> And even these algorithms can help asymptotic complexity
Is this a theorem or conjecture?
- stochastic_monk 9y agoExisting quantum algorithms have not yet been found which have reduced NP-complete problems to polynomial time. (See [0] for a pretty comprehensive list.) IE, I was talking about quantum algorithms we have, none of which have done so, not stating the impossibility of such an algorithm. I am not aware of a proof that comments on whether or not such an algorithm is impossible, however. [0]: https://math.nist.gov/quantum/zoo/ https://math.nist.gov/quantum/zoo/