The network complexity and the Turing machine complexity of finite functions期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

The network complexity and the Turing machine complexity of finite functions

Authors:	C P Schnorr

Affiliation:	(1) Fachbereich Mathematik, Universität Frankfurt, Robert-Mayer Str. 10, D-6000 Frankfurt/M., Germany

Abstract:	Summary 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. T _p (n) is the time bound and S _p 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) ² ²⁺) for every O.The results of this paper have been reported in a main lecture at the 1975 annual meeting of GAMM, April 2–5, Göttingen

Keywords:
本文献已被 SpringerLink 等数据库收录！