Complexity of verification and computation for IBC problems

DOI10.1016/0885-064X(92)90011-YMaRDI QIDQ1194380zbMATH OpenOpenAlexFDO

Authors 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)90011-y

zbMATH Keywords

Banach spacecomplexity of computationcomputingerror toleranceGaussian measureinformation-based complexitylinear continuous functionalprobabilistic complexityverifyingworst case complexity

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 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.

Recommendations

• Relaxed verification for continuous problems
• Perspectives on information-based complexity
• Probabilistic setting of information-based complexity
• There exists a problem whose computational complexity is any given function of the information complexity
• Recent developments in information-based complexity

Cites work

• Average case complexity of multivariate integration
• Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
• Gaussian measures in Banach spaces
• scientific article; zbMATH DE number 3688714 (Why is no real title available?)
• scientific article; zbMATH DE number 3755545 (Why is no real title available?)
• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Relaxed verification for continuous problems

Cited in

(4)

• Relaxed verification for continuous problems
• Testing linear operators -- an average case study
• Testing nonlinear operators
• Testing linear operators

This page was built for publication: Complexity of verification and computation for IBC problems

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