Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses

Xiaoyang Gu, John M. Hitchcock, A. Pavan

This paper presents the following results on sets that are complete for NP. 1. If there is a problem in NP that requires exponential time at almost all lengths, then every many-one…