Re:1931: Kurt Gödel shows limits of math, logic, computing, AI
by chriswarbo on Thursday June 17, 2021 @11:02AM
(#27540318)
Yeah, there are all sorts of layers we can add, especially regarding complexity (i.e. resource usage limits, rather than simple yes/no questions of decidability).
It's interesting to consider P = NP as a physical law, although that's certainly more tenuous than the Church-Turing thesis, etc.
I believe that quantum computation is a richer more powerful theory. In essence BQP is a superset of BPP in your link.
I think this happens with all sorts of mathematical objects. Non commutative algebra is much richer than commutative algebra. There are also more interesting non commutative things than just deformations of classical objects. Its the classical commutative case that is the weird limit.