Relaxed verification for continuous problems

DOI10.1016/0885-064X(92)90012-ZMaRDI QIDQ1194381zbMATH OpenOpenAlexFDO

Authors Erich Novak, H. Woźniakowski

Publication date 27 September 1992

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064x(92)90012-z

zbMATH Keywords

computation complexityinformation-based complexityverification complexityworst-case setting

Mathematics Subject Classification ID

General theory of numerical analysis in abstract spaces (65J05) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• Complexity of verification and computation for IBC problems
• On verified numerical computations in convex programming
• scientific article; zbMATH DE number 5567958
• Rigorous verification of feasibility
• Epsilon-inflation in verification algorithms

Cites work

• Complexity of verification and computation for IBC problems

Cited in

(6)

• Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
• Complexity of verification and computation for IBC problems
• Testing linear operators -- an average case study
• Testing nonlinear operators
• Testing linear operators
• Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces

This page was built for publication: Relaxed verification for continuous problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1194381)