3 ms·
P vs NP can be expressed using Turing machines. However, reversible languages like Janus can only execute injective functions whereas a Turing machine can also
by float4 6y ago
P vs NP can be expressed using Turing machines. However, reversible languages like Janus can only execute injective functions whereas a Turing machine can also execute non-injective functions. This is why reversible Turing completeness, or r-Turing completeness, was invented[0] to further work on reversible languages.
As P vs NP has to do with Turing machines, not just reversible Turing machines, it's not really that comparable as far as I know.
There is some comparison that can be made between TMs and RTMs if you have multiple memory tapes, but I forgot what it was. Could be that that was also described in [0], but I don't know.
[0] "What do reversible programs compute?" from Axelsen et al.