3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Perhaps you should take a look at inductive counting, which is used to prove $\operatorname{NL}=\operatorname{coNL}$. $\endgroup$
    – Yuval Filmus
    Commented Oct 9, 2013 at 3:51
  • $\begingroup$ 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. $\endgroup$
    – Thomas Klimpel
    Commented Oct 10, 2013 at 10:51

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.