DocumentCode :
935687
Title :
On the power of straight- line computations in finite fields
Author :
Lempel, Abraham ; Seroussi, Gadiel ; Ziv, Jacob
Volume :
28
Issue :
6
fYear :
1982
fDate :
11/1/1982 12:00:00 AM
Firstpage :
875
Lastpage :
880
Abstract :
It is shown that a lower hound of 
or more on the straight-line complexity of a function 
over GF 
is also a lower bound on the network complexity of and, 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.
or more on the straight-line complexity of a function over GF is also a lower bound on the network complexity of and, 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.Keywords :
Galois fields; Approximation algorithms; Arithmetic; Boolean functions; Computational complexity; Computer networks; Computer science; Galois fields; Information theory; Jacobian matrices; Turing machines;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.1982.1056592
Filename :
1056592
Link To Document :
