On the power of straight- line computations in finite fields
Abraham Lempel, G. Seroussi, J. Ziv · IEEE Transactions on Information Theory · 1982
It is shown that a lower hound ofn^{3}or more on the straight-line complexity of a functionfover GF(2^{n})is also a lower bound on the network complexity offand, hence, on the product of run time and program size of Turing machines. It is further shown that most functions over a finite field are hard to compute and that for most hard functions there exists no approximation via an easy algorithm.