• DocumentCode
    3379884
  • Title

    If NP languages are hard on the worst-case then it is easy to find their hard instances

  • Author

    Gutfreund, Dan ; Shaltiel, Ronen ; Ta-Shma, Amnon

  • Author_Institution
    Sch. of Comput. Sci. & Eng., Hebrew Univ. of Jerusalem, Israel
  • fYear
    2005
  • fDate
    11-15 June 2005
  • Firstpage
    243
  • Lastpage
    257
  • Abstract
    We prove that if NP
  • Keywords
    Boolean functions; computability; computational complexity; formal languages; statistical distributions; Boolean formula; NP-complete language; OWF; SAT; cryptography; polynomially samplable distribution; probabilistic polynomial time algorithm; quasipolynomial time; satisfiability; worst-case hard language; Computational complexity; Computer science; Cryptography; Information technology; NP-complete problem; Polynomials; Scholarships; Stress; Time measurement;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on
  • ISSN
    1093-0159
  • Print_ISBN
    0-7695-2364-1
  • Type

    conf

  • DOI
    10.1109/CCC.2005.11
  • Filename
    1443090
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3379884