  We study classical query algorithms with post-selection, and find that they
are closely connected to rational functions with nonnegative coefficients. We
show that the post-selected classical query complexity of a Boolean function is
equal to the minimal degree of a rational function with nonnegative
coefficients that approximates it (up to a factor of two). For post-selected
quantum query algorithms, a similar relationship was shown by Mahadev and de
Wolf, where the rational approximations are allowed to have negative
coefficients. Using our characterisation, we find an exponentially large
separation between post-selected classical query complexity and post-selected
quantum query complexity, by proving a lower bound on the degree of rational
approximations (with nonnegative coefficients) to the Majority function. This
lower bound can be generalised to arbitrary symmetric functions, and allows us
to find an unbounded separation between non-deterministic quantum and
post-selected classical query complexity. All lower bounds carry over into the
communication complexity setting.
  We show that the zero-error variants of post-selected query algorithms are
equivalent to non-deterministic classical query algorithms, which in turn are
characterised by nonnegative polynomials, and for some problems require
exponentially more queries to the input than their bounded-error counterparts.
Finally, we describe a post-selected query algorithm for approximating the
Majority function, and an efficient query algorithm for approximate counting.
