Implicit Computation: an Output-Polynomial Algorithm for Evaluating Straight-Line Programs

Shahoumian, Troy A.

HP Development Company

关键词: theory of computation;    randomized algorithms;    straight-line programs;    output-polynomial algorithms;   

RP-ID  :  HPL-1999-25

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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. 6 Pages