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.