# Is the time reversal symmetry of non-deterministic computations important?

A deterministic computation can only be run backward in time, if all transitions are one-to-one. This restriction is absent for non-deterministic computations. Hence it seems to me that non-deterministic computations be can run both forward and backward in time. But because the output becomes the input for the reversed computation, and the only output for a decision problem is "yes"/"no", this time reversal symmetry seems pretty useless for decision problems.

Now I wonder whether there is some class of computational problems for which this fact would translate into a corresponding useful property. Something like the fact that "P = co-P", which is a useful property of decision problems for deterministic computations.

Is there a computational problem type for which the time reversal symmetry of non-deterministic computations turns into a useful property for certain problem classes?

The computational problem types I have in mind here are the different types of requested output like

• decision problem
• optimization problem
• search problem
• counting problem
• function problem

because the different types of expected input (that come to my mind) like

• offline/online problem
• (non-)promise problem

seem to be closely tied to the computational problem itself, so that they are probably not helpful for general symmetry considerations.

• Perhaps you should take a look at inductive counting, which is used to prove $\operatorname{NL}=\operatorname{coNL}$. – Yuval Filmus Oct 9 '13 at 3:51
• Thanks for this suggestion. I now read this nice and instructive proof, and plan to also read some related proofs like Savitch's theorem. However, I noticed that this proof is "non-trivial" and not directly related to the possibility to run non-deterministic computations backward in time. Hence I edited my question to clarify that I'm mostly interested in whether the time reversal symmetry of non-deterministic computation leads to something useful. – Thomas Klimpel Oct 10 '13 at 10:51

This raises the question whether deterministic context-free languages are closed under the reversal of $L$, because this is the only one of the examples where the deterministic and the non-deterministic languages are not identical.