计算
来看一段用伪代码写的简单程序:
算法 1:运算取决于输入
function calc(w, a, b)
if w then
return a * b
else
return a + b
end if
end function
从高层次的角度来看,这段程序和我们协议里的多项式并没有什么关系。我们现在需要找到一种方式来将程序转换成多项式形式。第一步是将程序转换成数学语言,这个相对简单一些,声明可以表达成下面的形式(假定 \(w\) 是 0 或 1):
$$f(w, a, b) = w (a \times b) + (1 - w) (a + b)$$
执行 calc(1, 4, 2)
和对 \(f(1, 4, 2)\) 求值都可以得到相同的结果:8。如果执行 calc(0, 4, 2)
和 \(f(0, 4, 2)\) 也都能得到 6。其实我们可以用这种方法表达任何形式的有限程序。
接下来需要我们证明的是(在这个例子中),对于表达式 \(f(w, a, b)\) ,输入为 \((1, 4, 2)\) 时的输出是否为 8,换句话说,我们需要检查下面的相等性:
$$w (a \times b) + (1 - w) (a + b) = 8$$
译者注:猜想一下,只要是能用多项式表示的程序都可以做证明吗?