3 ms·
What complexity class describes these computing devices?
by Ar-Curunir 7y ago
What complexity class describes these computing devices?
- fooker 7y agohttps://en.wikipedia.org/wiki/PP_(complexity) https://en.wikipedia.org/wiki/PP_(complexity)
- marris 7y agoPP 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.
- Ar-Curunir 7y agoAre they claiming that they have a computer that shows BPP = PP? That's absurd.