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 [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:
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 thenCase 1: F and x are such that F(C_{x}) = F(z). For such inputs, the claim clearly holds.
- if p_{v} outputs 0 for these inputs, so does p_{w}, and
- if p_{v} outputs 1 for these inputs, p_{w} outputs 2^{x}.
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.