3 ms·
PP implies that that computation runs for a polynomial number of steps before producing its probabilistic answer. In the article description, the computation se
by marris 7y ago
PP implies that that computation runs for a polynomial number of steps before producing its probabilistic answer. In the article description, the computation seems to be run "until the answer is separated from the noise." And although they are hopeful, I don't think they are asserting at the moment that this will happen after a polynomial number of steps. So PP would not apply.
- Khoth 7y agoIf it happens in a polynomial number of steps on average, but you might get unlucky, https://en.wikipedia.org/wiki/ZPP_(complexity) https://en.wikipedia.org/wiki/ZPP_(complexity) If it can just take as long as they want, then the probabilistic part is basically irrelevant and you're probably looking at https://en.wikipedia.org/wiki/PSPACE https://en.wikipedia.org/wiki/PSPACE In any case, I very much doubt they'd made any real breakthrough in factoring numbers.