ItA 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 Turing machinescomputations be can run algorithmsboth forward and backward-in-time 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 howwhether there is some class of computational problems for which this fact couldwould translate into a corresponding closure or symmetryuseful property of some class of computational problems. Something like the fact that "P = co-P" for decision problem, which tells us something about symmetries related tois a useful property of decision problems for deterministic Turing machinescomputations.
Is there a computational problem type for which the backward-in-timetime reversal symmetry of non-deterministic Turing machinescomputations turns into a simple closureuseful 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.