Classical query algorithm

A classical query algorithm is a finite decision procedure for a fixed encoded instance length $n$ and explicitly declared public data $p$, whose query actions are to the total function $f_z$ of Promise query instance and oracle family. The procedure is fixed independently of the hidden instance $z$ at fixed $(n,p)$. Its encoding in Input encoding and size for algorithmic tasks labels the instance and determines its size; it does not provide a readable copy of the hidden encoding. Each query chooses an address from $n,p$, earlier replies, and any random bits used so far; it receives the entire $b(n)$-bit reply $f_z(x)$ as one query answer. The address choices may be adaptive. Its terminal output is determined by the same public data, replies, and random tape.

In the ordinary oracle-only model, all dependence on the hidden instance is through these replies. Public parameters such as register widths, a supplied marked count, or an explicit arithmetic input may be used only when the task declares them. A lower bound in the oracle-only model fixes the declared public data across the hidden instances it compares. Additional input-access or preparation capabilities must be explicitly declared with their charges; they are extra resources, not supplied by the hidden instance encoding.

For a randomized algorithm, each branch is determined by the public data, oracle replies, and its finite random tape; the fair-bit tape convention for a bounded-time probabilistic machine is supplied by Probabilistic polynomial time machine interface. The query model itself imposes no polynomial bit-time bound. A query bound is a worst-case bound over promised inputs and every random branch; classical computation between queries is charged separately only when a bit-cost model is specified.