TY - GEN
T1 - On average case complexity of problems that are intractable in the worst case
AU - Wasilkowski, G. W.
PY - 1992
Y1 - 1992
N2 - The worst case setting seems to be the most important setting for studying complexity of approximately solved problems. Unfortunately, some problems of practical importance are intractable or even unsolvable in the worst case setting and to cope with the inherent difficulty of such problems one has to switch to other settings. A natural alternative is provided by the average case setting under which worst case intractable and/or unsolvable problems become tractable. In this paper we will discuss some results on multivariate integration and function approximation and show by how much the complexity is reduced when the average case is utilized.
AB - The worst case setting seems to be the most important setting for studying complexity of approximately solved problems. Unfortunately, some problems of practical importance are intractable or even unsolvable in the worst case setting and to cope with the inherent difficulty of such problems one has to switch to other settings. A natural alternative is provided by the average case setting under which worst case intractable and/or unsolvable problems become tractable. In this paper we will discuss some results on multivariate integration and function approximation and show by how much the complexity is reduced when the average case is utilized.
UR - http://www.scopus.com/inward/record.url?scp=0027091504&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027091504&partnerID=8YFLogxK
U2 - 10.23919/acc.1992.4792069
DO - 10.23919/acc.1992.4792069
M3 - Conference contribution
AN - SCOPUS:0027091504
SN - 0780302109
SN - 9780780302105
T3 - Proceedings of the American Control Conference
SP - 265
EP - 269
BT - Proceedings of the American Control Conference
T2 - Proceedings of the 1992 American Control Conference
Y2 - 24 June 1992 through 26 June 1992
ER -