查看文章

This paper lies on the border between logic and complexity theory, and is intended to illuminate both fields. We introduce a new notion, that of “feasible functional”, and use it to analyze logica. theories which are supposed to capture the concept of polynomial time reasoning. Functionals are functions which take natural numbers and other functionals as a. rguments, and return natural numbers as values. Type 1 functionals take only numbers as arguments, type 2 functionals take both numbers and type 1 functionals as arguments, and in general type h+ 1 functionals take numbers and functionals of type L or less as arguments. The “feasible functional? a. re those which can be computed “in polynomial time”. The difficulty in making this precise lies in answering “time polynomial in what?” The answer given by Buss [3] is time polynomial in the length of a progra, m computing the input functional. This notion suited Buss …