On average case complexity of problems that are intractable in the worst case

G. W. Wasilkowski

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the American Control Conference
Pages265-269
Number of pages5
DOIs
StatePublished - 1992
EventProceedings of the 1992 American Control Conference - Chicago, IL, USA
Duration: Jun 24 1992Jun 26 1992

Publication series

NameProceedings of the American Control Conference
Volume1
ISSN (Print)0743-1619

Conference

ConferenceProceedings of the 1992 American Control Conference
CityChicago, IL, USA
Period6/24/926/26/92

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'On average case complexity of problems that are intractable in the worst case'. Together they form a unique fingerprint.

Cite this