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 -