Determining whether two programs always return same output for same input is undecidable (easily reduced to the halting problem). My question is, is there a complexity class in which this problem is decidable for machines on that class?

Seems like it must be below PTIME, as Datalog is P-Complete and equivalence of Datalog programs is undecidable.

  • $\begingroup$ What do you mean by "complexity class"? Does the class of regular languages count as one, for instance? Note that not all complexity classes have a machine model that correspond to them. $\endgroup$ – dkaeae Jul 16 '19 at 16:18
  • $\begingroup$ Your question contains a category error. Complexity classes are classes of problems (e.g., "Is this graph 3-colourable"), not classes of programs (e.g., algorithms which may or may not compute 3-colourings of graphs"). $\endgroup$ – David Richerby Jul 16 '19 at 17:17
  • $\begingroup$ they're classes of programs too - all machines that run in say polynomial time wrt the input size. im just talking from descriptive complexity point of view $\endgroup$ – Troy McClure Jul 16 '19 at 20:30
  • $\begingroup$ more explicitly and for example, one can take any machine that runs in PTIME and convert it into a datalog program. if we could decide equivalence of any two PTIME machines, then we could decide equivalence of datalog programs. therefore such is undecidable $\endgroup$ – Troy McClure Jul 16 '19 at 21:25

Given a Turing machine $M$, we can construct another Turing machine $T$, which on input $1^n$ simulates $M$ for $\log n$ steps, and returns whether $M$ halted within these steps. The new Turing machine runs in linear time, and is equivalent to the constant time Turing machine which always returns "No" iff $M$ doesn't halt. Therefore program equivalence is undecidable even for linear time Turing machines.

  • $\begingroup$ sorry but im sure im missing something here. can you please elaborate a little more? $\endgroup$ – Troy McClure Jul 16 '19 at 23:22
  • $\begingroup$ @TroyMcClure if ive gotten the argument right, Yuval is saying « the turing machine that decides program equivalence could solve the halting problem » $\endgroup$ – D. Ben Knoble Jul 17 '19 at 0:14
  • $\begingroup$ @TroyMcClure Above $M$ is any arbitrary TM. TM $T$ simultaes $M$ only for $\log n$ steps, so $T$ has linear complexity, no matter what $M$ is. If $M$ does not halt, $T$ will answer "no" to all inputs. If $M$ halts, $T$ will answer "no" for small inputs, and "yes" for large enough inputs. So, if we can decide the equivalence of the linear-time $T$ with the constant time "always no" TM, we decide the halting problem on any $M$. $\endgroup$ – chi Jul 17 '19 at 11:42
  • $\begingroup$ but it can solve the halting problem only for M and even that is after we constructed a machine that solves the halting problem for M (so we already know whether M halts). or im missing something $\endgroup$ – Troy McClure Jul 17 '19 at 12:50

Reversal Bounded Counter Automata have decidable equivalence. They're a fascinating class, because augmenting them in any obvious way makes one of their main properties (equivalence, emptiness, etc.) undecidable. Oscar Ibarra's work explored their properties extensively: http://www.lsv.ens-cachan.fr/~demri/Ibarra78.pdf

If I recall correctly, visibly pushdown Automata also have decidable equivalence, though I'm as familiar with that class.

  • $\begingroup$ what can we tell about their expressive power? $\endgroup$ – Troy McClure Jul 17 '19 at 14:46
  • $\begingroup$ @TroyMcClure They're not comparable with Context Free languages i.e. more powerful in some respects, weaker in others. I think in the unary case they're equivalent to Presburger arithmetic, but I don't remember the reference for that offhand. $\endgroup$ – jmite Jul 17 '19 at 17:58
  • $\begingroup$ thanks, so it doesn't correspond to any standard complexity class? $\endgroup$ – Troy McClure Jul 17 '19 at 18:23
  • $\begingroup$ @TroyMcClure the class accepted by the deterministic variant at least is a subset of P. $\endgroup$ – jmite Jul 17 '19 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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