4 ms·
How does that relate to P versus NP problem?
by miguelrochefort 6y ago
How does that relate to P versus NP problem?
- wizzwizz4 6y agoIt doesn't. (Probably.)
- float4 6y agoP 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.
- karlicoss 6y agoWhile it doesn't relate directly, but quantum computing (which is reversible) is represented by BQP complexity class, which contains P, but it's still unclear how it relates to NP.