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 .) 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:
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).
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
Case 1: F and x are such that F(Cx) = F(z). For such inputs, the claim clearly holds.
- if pv outputs 0 for these inputs, so does pw, and
- if pv outputs 1 for these inputs, pw outputs 2x.
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
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.
Back to the list of talks