Relaxed verification for continuous problems (Q1194381)

The authors analyze the complexity of verifying whether a given element is close to a solution element. Closeness is measured by two nonnegative parameters \(\varepsilon\) and \(\alpha\). If \(\alpha=0\) the authors get the strong verification problem which usually cannot be solved in the worst- case setting [cf. the second author, ibid. 8, No. 2, 93-123 (1992; reviewed below)]. The case \(\alpha>0\) is studied in this paper. Complexity bounds for the \((\varepsilon,\alpha)\)-verification problem are also derived.