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.
The time reversal symmetry is already important for decision problems. It translates into reversal of the accepted language. The trick is to replace total functions by partial functions, and don't consider "yes"/"no" as output of the problem. Instead, the "yes"/"no" is derived from the existence of a path between start and end state. This is explained for finite automata in my answer to the question "Why is non-determinism useful concept?", and elaborated for more powerful machines like pushdown automata, Turing machines and probabilistic machines in my answer to the question "What is the difference between non-determinism and randomness?".

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.

The importance of the time reversal symmetry is not necessarily limited to the decision problem. It might be possible to also work out its consequences for the counting problem and the function problem.