On the Zero-inequivalence Problem far Loop Programs

摘要

The complexity of the zero-inequivalence problem (deciding if a program outputs a nonzero value for some nonnegative integer input) for several simple classes of loop programs is studied. In particular, we show that the problem is NP-complete for L1-programs with only one input variable and two auxiliary variables. These are programs over the instruction set x ← 0, x ← x + 1, x ← y, do x … end, where do-loops cannot be nested. For K1-programs, where the instruction set is x ← x + 1, x ← x ∸ 1, do x … end, zero-inequivalence is NP-complete even for programs with only one input variable and one auxiliary variable. These results may be the best possible since there is a class of programs which properly contains two-variable L1-programs and one-variable K1-programs with a polynomial time decidable equivalence problem. Addition of other constructs, e.g., allowing K1-programs to use instruction x ← x + y, makes the zero-inequivalence problem undecidable.