HP Labs Technical Reports
Click here for full text:
Implicit Computation: an Output-Polynomial Algorithm for Evaluating Straight-Line Programs
Shahoumian, Troy A.
Keyword(s): theory of computation; randomized algorithms; straight-line programs; output-polynomial algorithms
Abstract: Inputless straight-line programs using addition, subtraction and multiplication are considered. An output-polynomial algorithm is given for computing the output of such a program. The program runs in time polynomial in the length of the program and the length of its output. As a consequence, even if intermediate results are exponentially longer than the program, the output can be computed efficiently when the output's size is small. This algorithm also applies to programs with integral inputs if the size of the inputs are considered to be part of the program's size.
Back to Index