Complexity of verification and computation for IBC problems
type: Item
instance of: scholarly article
title: Complexity of verification and computation for IBC problems
zbMATH Open document ID: 0755.65149
DOI: 10.1016/0885-064X(92)90011-Y
published in: Journal of Complexity
publication date: 1992-09-27T00:00:00Z
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.
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 65J05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 64311
zbMATH Keywords: verifying
zbMATH Keywords: computing
zbMATH Keywords: worst case complexity
zbMATH Keywords: probabilistic complexity
zbMATH Keywords: error tolerance
zbMATH Keywords: linear continuous functional
zbMATH Keywords: Banach space
zbMATH Keywords: Gaussian measure
zbMATH Keywords: complexity of computation
zbMATH Keywords: information-based complexity
author: H. Woźniakowski
MaRDI profile type: Publication
cites work: Q4198056
cites work: Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
cites work: Gaussian measures in Banach spaces
cites work: Relaxed verification for continuous problems
cites work: Q3993279
cites work: Q3883494
cites work: Q3938928
cites work: Average case complexity of multivariate integration
full work available at URL: 0885-064x(92)90011-y
OpenAlex ID: W2133277606
description: scientific article; zbMATH DE number 64311