The network complexity and the Turing machine complexity of finite functions

Research paper by C. P. Schnorr

Indexed on: 01 Mar '76Published on: 01 Mar '76Published in: Acta Informatica


Let L(f) be the network complexity of a Boolean function L(f). For any n-ary Boolean function L(f) let \(TC(f) = min\{ T_p^{\bar A} (n){\text{ (}}\parallel p\parallel + 1gS_p^{\bar A} {\text{(}}n{\text{):}}res_p^{\bar A} {\text{(}}n{\text{) = }}f\} \). Hereby p ranges over all relative Turing programs and Ā ranges over all oracles such that given the oracle Ā, the restriction of p to inputs of length n is a program for L(f). ∥p∥ is the number of instructions of p. TpĀ(n) is the time bound and SpĀof the program p relative to the oracle Ā on inputs of length n. Our main results are (1) L(f) ≦ O(TC(L(f))), (2) TC(f) ≦ O(L(f)22+ɛ) for every ɛ ⋙ O.