@article{doi:10.1137/0211002,
    Abstract = {We consider a simple class of loop-free programs whose instruction repertoire consists of \$x \leftarrow 0\$, \$x \leftarrow c\$, \$x \leftarrow cx\$, \$x \leftarrow x/c\$, \$x \leftarrow x + y\$, \$x \leftarrow x - y\$, \$\textbf{skip } l\$, \$\textbf{if } p(x,y)\$\$\textbf{then skip }l\$, and \$\textbf{halt}\$. (x and y are integer variables, c is a positive integer, \$x/c\$ is integer division, l is a nonnegative integer, and \$p(x,y)\$ is a predicate of the form \$x > y\$, \$x \geqq y\$, \$x = y\$, \$x \ne y\$, \$x \leqq y\$, or \$x < y\$; \$\textbf{skip }l\$ causes the \$(l + 1)\$st instruction following the current instruction to be executed next.) We show that the equivalence problem for this class is decidable in \$2^{\lambda N^2 } \$ time (\$N = \$ sum of the sizes of the programs and \$\lambda \$ is a fixed positive constant). The bound cannot be reduced to a polynomial in N unless \${\text{P}} = {\text{NP}}\$. In fact, we have the following rather surprising result: The equivalence problem for programs with one input variable (which also serves as the output variable) and one auxiliary variable using only instructions \$x \leftarrow 2x\$, \$x\leftarrow x/2\$, and \$x \leftarrow x + y\$ is NP-hard.},
    Author = {Ibarra, Oscar H. and Leininger, Brian S.},
    EPrint = {https://doi.org/10.1137/0211002},
    File = {The Complexity of the Equivalence Problem for Simple Loop-Free Programs - ibarra1982.pdf},
    Journal = {SIAM Journal on Computing},
    Number = {1},
    Pages = {15--27},
    Title = {The Complexity of the Equivalence Problem for Simple Loop-Free Programs},
    URL = {https://doi.org/10.1137/0211002},
    Volume = {11},
    Year = {1982},
    bdsk-url-1 = {https://doi.org/10.1137/0211002},
    date-added = {2023-08-26 10:40:09 +0200},
    date-modified = {2023-08-26 10:40:15 +0200},
    doi = {10.1137/0211002}
}

@article{doi:10.1137/0211002, Abstract = {We consider a simple class of loop-free programs whose instruction repertoire consists of \$x \leftarrow 0\$, \$x \leftarrow c\$, \$x \leftarrow cx\$, \$x \leftarrow x/c\$, \$x \leftarrow x + y\$, \$x \leftarrow x - y\$, \$\textbf{skip } l\$, \$\textbf{if } p(x,y)\$\$\textbf{then skip }l\$, and \$\textbf{halt}\$. (x and y are integer variables, c is a positive integer, \$x/c\$ is integer division, l is a nonnegative integer, and \$p(x,y)\$ is a predicate of the form \$x > y\$, \$x \geqq y\$, \$x = y\$, \$x \ne y\$, \$x \leqq y\$, or \$x < y\$; \$\textbf{skip }l\$ causes the \$(l + 1)\$st instruction following the current instruction to be executed next.) We show that the equivalence problem for this class is decidable in \$2^{\lambda N^2 } \$ time (\$N = \$ sum of the sizes of the programs and \$\lambda \$ is a fixed positive constant). The bound cannot be reduced to a polynomial in N unless \${\text{P}} = {\text{NP}}\$. In fact, we have the following rather surprising result: The equivalence problem for programs with one input variable (which also serves as the output variable) and one auxiliary variable using only instructions \$x \leftarrow 2x\$, \$x\leftarrow x/2\$, and \$x \leftarrow x + y\$ is NP-hard.}, Author = {Ibarra, Oscar H. and Leininger, Brian S.}, EPrint = {https://doi.org/10.1137/0211002}, File = {The Complexity of the Equivalence Problem for Simple Loop-Free Programs - ibarra1982.pdf}, Journal = {SIAM Journal on Computing}, Number = {1}, Pages = {15--27}, Title = {The Complexity of the Equivalence Problem for Simple Loop-Free Programs}, URL = {https://doi.org/10.1137/0211002}, Volume = {11}, Year = {1982}, bdsk-url-1 = {https://doi.org/10.1137/0211002}, date-added = {2023-08-26 10:40:09 +0200}, date-modified = {2023-08-26 10:40:15 +0200}, doi = {10.1137/0211002} }