论文部分内容阅读
直线程序对计算树模型是两个研究环(或域)上代数问题复杂性的较好的计算模型,特别是对问题复杂性下界的研究是很方便的。对任何一个直线程序Г,存在一个通用输入(U;u),使得对Г的任何其它可执行的输入(A:a),(A;a)是(U;u)的一个同态象。给出一个求直线程序通用输入的算法和一个计算实例。