Average-Case Intractability vs. Worst-Case Intractability

Johannes Köbler Rainer Schuler

Published in: Electron. Colloquium Comput. Complex. (1998)

Keyphrases

average case
worst case
worst case analysis
np complete
uniform distribution
learning curves
np hard
upper bound
vc dimension
lower bound
greedy algorithm
approximation algorithms
special case
average case complexity
state space
sample size