Carnegie Mellon University
Browse

Hardness amplification within NP

Download (341.65 kB)
journal contribution
posted on 1983-01-01, 00:00 authored by Ryan O'Donnell
In this paper we investigate the following question: if NP is slightly hard on average, is it very hard on average? The computational result we prove essentially matches an information-theoretic bound

History

Publisher Statement

All Rights Reserved

Date

1983-01-01