However, the inversion of the universe’s forward passes can be NP-complete functions. Hence a lot of difficulties.
If were talking about cryptography specifically, we don’t believe that the inversion of the universe’s forward passes for cryptography is NP-complete, and if this was proved, this would collapse the polynomial hierarchy to the first level. The general view is that the polynomial hierarchy is likely to have an infinite amount of levels, ala Hilbert’s hotel.
Yup! Cryptography actually was the main thing I was thinking about there. And there’s indeed some relation. For example, it appears that NP≠P is because our universe’s baseline “forward-pass functions” are just poorly suited for being composed into functions solving certain problems. The environment doesn’t calculate those; all of those are in P.
A different story is that the following constraints potentially prevent us from solving NP-complete problems efficiently:
The first law of thermodynamics coming from time-symmetry of the universe’s physical laws.
Light speed being finite, meaning there’s only a finite amount of universe to build your computer.
Limits on memory and computational speed not letting us scale exponentially forever.
(Possibly) Time Travel and Quantum Gravity are inconsistent, or time travel/CTCs are impossible.
Edit: OTCs might also be impossible, where you can’t travel in time but nevertheless have a wormhole, meaning wormholes might be impossible.
.
If were talking about cryptography specifically, we don’t believe that the inversion of the universe’s forward passes for cryptography is NP-complete, and if this was proved, this would collapse the polynomial hierarchy to the first level. The general view is that the polynomial hierarchy is likely to have an infinite amount of levels, ala Hilbert’s hotel.
A different story is that the following constraints potentially prevent us from solving NP-complete problems efficiently:
The first law of thermodynamics coming from time-symmetry of the universe’s physical laws.
Light speed being finite, meaning there’s only a finite amount of universe to build your computer.
Limits on memory and computational speed not letting us scale exponentially forever.
(Possibly) Time Travel and Quantum Gravity are inconsistent, or time travel/CTCs are impossible.
Edit: OTCs might also be impossible, where you can’t travel in time but nevertheless have a wormhole, meaning wormholes might be impossible. .