HP Labs Technical Reports
Click here for full text:
Implicit Computation: an OutputPolynomial Algorithm for Evaluating StraightLine Programs
Shahoumian, Troy A.
HPL199925
Keyword(s): theory of computation; randomized algorithms; straightline programs; outputpolynomial algorithms
Abstract: Inputless straightline programs using addition, subtraction and multiplication are considered. An outputpolynomial 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.
6 Pages
Back to Index
