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

## James S. RoyerSyracuse 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 , , , , , and .

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.

Background

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 .) 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:

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

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  or . QED

Claim 2. W is not basic feasible.

Proof. Suppose we restrict F to be 0-1 valued. It follows from  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.

Discussion
• Intuitively, W is feasible (in its arguments) because if W observes that F(Cx) != F(z), then W can infer that the procedure for F, call it pF, made a particular (big) query of its type-1 argument and so W can output this (big) query in time commensurate with pF's run-time. So, even though F is a black box which many be 0-1 valued, information about the run-time of pF can leak out. This sort of information leaking is a well-known (and problematic) phenomenon in the classical theory of type-3 computability, see  and .
• 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  and , 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.

References
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
USA
Email: royer@top.cis.syr.edu