Carnegie Mellon University
Browse
file.pdf (341.65 kB)

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

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC