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

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:

• N denotes the natural numbers.
• A type-1 function is a function of the type N->N.
• A type-2 functional is one of the type
    (N->N) -> N    or
    (N->N) x N->N.
• A type-3 functional is one of the type
    (type-2 stuff) x (N->N) x N - >N    or
    (type-2 stuff) x N -> N.

The example depends on the following fact.

Fact. Deciding [2^x=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, [2^x=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 C_x denote the characteristic function of 2^x.

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

Other Notation. In the following:

• F ranges over (N->N)->N.
• x ranges over N.
• ``!='' means not equal.
• z:N->N denotes the everywhere 0 function.

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

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

W(F,x) = 2^x, if F(C_x) != F(z).
W(F,x) = 0,  if F(C_x) = 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 p_v for V, there is a program p_w for W such that, in any reasonable, purely computational experiment, one has that, for all F and x, the run-time of p_w on (F,x) is no more than twice the run-time of p_v 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 p_v and p_w 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 p_v (respectively, p_w) 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 p_v. The program p_w on inputs (F,x) will simply run p_v on these inputs and then

1. if p_v outputs 0 for these inputs, so does p_w, and
2. if p_v outputs 1 for these inputs, p_w outputs 2^x.

Case 1: F and x are such that F(C_x) = F(z). For such inputs, the claim clearly holds.

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

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.

• Intuitively, W is feasible (in its arguments) because if W observes that F(C_x) != F(z), then W can infer that the procedure for F, call it p_F, made a particular (big) query of its type-1 argument and so W can output this (big) query in time commensurate with p_F's run-time. So, even though F is a black box which many be 0-1 valued, information about the run-time of p_F can leak out. This sort of information leaking is a well-known (and problematic) phenomenon in the classical theory of type-3 computability, see [1] and [4].
• Claim 3 and the Aside need some formal backing to be fully rigorous. The most conservative approach I can think of is to develop a polynomial-time version of the theory of ``countable functionals,'' see [1] and [4], which is work I currently have in progress. As the work now stands, W fits comfortably within the ``polynomial-time countable functionals.'' However, it appears that this class of polynomial-time countable functionals may have its own problematic aspects. E.g., it is a nontrivial questions as to whether there is any reasonable indexing of this class.
• In higher-type computability theory, it is a common observation that ``bad things happen at type-3.'' Higher-type complexity theory seems to be in for its share of ``bad things'' at type-3. The challenge is to build a useful theory that takes full account of whatever good or bad things are awaiting us.

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

Back to the list of talks