Simon query lower bounds do not imply explicit-input gate lower bounds

Let $N=2^n$ and $L=nN+n+1$, the length of the unary-header table code. For each of the $\left(\genfrac{}{}{0px}{}{N}{2}\right)$ distinct address pairs, scan the table to retrieve both $n$-bit outputs and answer NO if they coincide; answer YES if no pair collides. On a promised table this is correct, since YES functions are injective and every NO function has a collision.

One table scan and output comparison take $O(L)$ transitions, so the $\left(\genfrac{}{}{0px}{}{N}{2}\right)$ pairs take $O(N^{2}L)$ time. Since $N\le L$, this is $O(L^3)$; the explicit-table promise problem is therefore in deterministic polynomial time under [F4].

The oracle bounds in [F1] and [F2] charge calls to $f$ or $U_f$, whereas the explicit-input algorithm charges table scans and ordinary computation as required by [F5]. The deterministic $O(L^3)$ algorithm in step 2.1 contradicts the asserted absence of a polynomial-in-$L$ algorithm. Thus this oracle-query separation does not imply superpolynomial classical running time in the explicit-input length. This comparison does not refute an $\mathrm{\Omega }(2^{n\mathrm{/}2})$ time bound measured in $n$: the explicit table already has length $L=n{2}^n+n+1$.