Complexity of verification and computation for IBC problems (Q1194380)

The author analyzes the complexity of verifying whether a given element is within \(\varepsilon\) of the solution element, which may be contrasted with the complexity of computing an element that is within \(\varepsilon\) of the solution element. In information-based-complexity (IBC), where the minimal cost of computing an \(\varepsilon\)-approximation to the solution element in different settings is studied, verification can be easier or harder than computation. The author studies the probabilistic complexity of verification as a function of the error tolerance \(\varepsilon\) and the probability failure \(\delta\). It is assumed that the solution element is specified by a linear continuous functional defined on a Banach space equipped with a Gaussian measure. It is shown that for fixed \(\delta\) and small \(\varepsilon\), the complexity of verification is zero, whereas for fixed \(\varepsilon\) and small \(\delta\) the complexity of verification is essentially a function of only \(\delta\) and may be exponentially harder than the complexity of computation.