A Feasible Type-3 Functional
That Fails to be Basic Feasible

James S. Royer
Syracuse University

The evidence that the type-2 basic feasible functionals correspond to the type-2 analog of polynomial-time is reasonably good. See for example [1], [2], [5], [6], [7], and [8].

We give an example that shows that the correspondence between the type-3 basic feasible functionals and type-3 polynomial-time is very problematic.

On Types. In this note:


The example depends on the following fact.

Fact. Deciding [2x=y] can be done in time O(|x|+|y|) on a multi-tape Turing Machine (where x and y are represented in binary).

Proof. Given x and y, [2x=y] is equivalent to y = 10...0 (base 2), where there are x-1 many 0's. Constructing the binary representation of the number of trailing 0's can be done in O(|y|) time. (See Chapter 18 of [3].) QED

For each x in N, let Cx denote the characteristic function of 2x.

Corollary. Given x and y, computing Cx(y) can be done in time O(|x|+|y|).

Other Notation. In the following:

The Example

For all F and x, define V and W thus.

V(F,x) = 1, if F(Cx) != F(z).
V(F,x) = 0, if F(Cx) = F(z).

W(F,x) = 2x, if F(Cx) != F(z).
W(F,x) = 0,  if F(Cx) = F(z).

Claim 1. V is basic feasible.

Proof. Using the Fact, it is straightforward to define V in the formalism for the basic feasible functionals of [1] or [2]. QED

Claim 2. W is not basic feasible.

Proof. Suppose we restrict F to be 0-1 valued. It follows from [5] that when F is so restricted, for each basic feasible U, there is a polynomial q such that for all F and x,

|U(F,x)|   <   q(|x|).
But W clearly fails to have this property. QED

Claim 3. V and W have roughly the same computational complexity. That is, given any program pv for V, there is a program pw for W such that, in any reasonable, purely computational experiment, one has that, for all F and x, the run-time of pw on (F,x) is no more than twice the run-time of pv on (F,x).

An Aside

Question: What in the world does ``in any reasonable, purely computational experiment'' mean?

Answer: Consider using an actual computer to run timing experiments on pv and pw for various inputs F and x. To do this, F would be represented by some procedure, x would be represented in binary, and the run-time of pv (respectively, pw) would be the total observed time between starting the program and the time the program halts. Hence, this total run-time includes the time costs of running the procedure for F.

Proof Sketch of Claim 3. Fix a pv. The program pw on inputs (F,x) will simply run pv on these inputs and then
  1. if pv outputs 0 for these inputs, so does pw, and
  2. if pv outputs 1 for these inputs, pw outputs 2x.
Case 1: F and x are such that F(Cx) = F(z). For such inputs, the claim clearly holds.

Case 2: F and x are such that F(Cx) != F(z). Observe that for all y in N, Cx(y)=z(y)=0 except when y=2x. Thus, since F(Cx) != F(z), any procedure for F (recall that we are assuming F is represented by a procedure) must actually write down 2x to make the query ``f(2x)=?'' of both Cx and z. Hence, the run-time of pv on this (F,x) already includes the cost of writing down 2x twice. Therefore, the cost of pw writing down 2x one more time for its output, at most doubles its run-time over that of pv. Hence, the claim holds in this case also. QED

Summary of the Example

We have two type-3 functionals V, which is basic feasible, and W, which is not, such that, in the sense outlined in the Aside, the computational complexity of W is O(the computational complexity of V), hence V and W have ``equivalent'' complexities.

Thus, if you agree with the answer in the Aside and if you admit V as feasible, then you also must admit the non-basic-feasible W as feasible.


  1. S.A. Cook. Computability and complexity of higher type functions. In Logic from Computer Science, Springer-Verlag (1991) 51-72.
  2. S.A. Cook and B.M. Kapron. Characterizations of the Basic Feasible Functions of Finite Type. In Feasible Mathematics: A Mathematical Sciences Institute Workshop, Birkhäuser (1990) 71-95.
  3. T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms, MIT Press, 1991.
  4. R. Gandy and J. Hyland. Computable and recursively countable functions of higher type. In Logic Colloquium 76, North-Holland (1977) 407-438.
  5. B.M. Kapron and S.A. Cook. A new characterization of type-2 feasibility. SIAM J. on Computing 25 (1996) 117-132.
  6. K. Mehlhorn. Polynomial and abstract subrecursive classes. J. Computing and System Science 12 (1979) 147-178.
  7. J.S. Royer. Semantics vs. syntax vs. computations. In Proceedings of the 10th Annual IEEE Structure in Complexity Conference (1995) 37-48.
  8. A. Seth. There is no recursive axiomatization for feasible functionals of type 2. In Proceedings of the 7th Annual IEEE Symposium on Logic in Computer Science (1992) 286-295.

James S. Royer

School of Computer and Inf. Science
Syracuse University
Syracuse, NY 13244
Email: royer@top.cis.syr.edu
Home page: http://www.cis.syr.edu/~royer/

Back to the list of talks