Re:Macroscopic quantum objects cannot exist if P ≠ NP?
by dllthomas on Friday July 25, 2014 @03:11PM
(#8087050)
'The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to.'
I totally agree, which is part of why the article didn't clear it up.
"Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve problems a TM can solve but asymptotically faster."
A Zeno machine, for sure. It is not immediately clear to me that this necessarily holds for anything that can solve the halting problem - what about a TM plus a halting problem oracle that would tell you in 2^(size of TM) whether a TM halts?
Of course the real question is whether asymptotically faster is enough to be "hypercomputation". Necessity is also interesting, but not the same thing.
Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve problems a TM can solve but asymptotically faster.