We investigate alternative notions of approximation for problems inside P (deterministic polynomial time). We show that for some natural problems, a barely non-trivial advantage over guessing is as hard to obtain as the solution itself. For example, we prove that if one could eliminate a single possibility for the value of an arithmetic circuit on a given input, then this would imply that the class P has fast (polygarithmic time) parallel algorithms. In other words, this would constitute a proof that there are no inherently sequential problems in P, which is quite implausible. The result is robust with respect to eliminating procedures that are even allowed to err (by excluding the correct value) with small probability.
We also show that several fundamental linear algebra problems are hard in this sense. It turns out to be as hard to substantially reduce the number of possible values for matrix rank and matrix determinant as to compute them exactly. This notion of approximation has been studied previously. This is the first time, however, it is investigated for functions inside P.
If time permits, we will show that (in some precise sense) randomness can be non-trivially substituted for nondeterminism in space-bounded computations.