Distributionally hard languages

DOI10.1007/S00224-001-0003-0MaRDI QIDQ5945724zbMATH OpenOpenAlexFDO

Authors Lance Fortnow, Aduri Pavan, Alan L. Selman

Publication date 11 September 2002

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-001-0003-0

zbMATH Keywords

average polynomial time

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Complete distributional problems, hard languages, and resource-bounded measure
• scientific article; zbMATH DE number 1114051
• Complexity of distributions and average-case hardness
• On the theory of average case complexity
• scientific article; zbMATH DE number 512870

Cited in

(2)

• Properties of uniformly hard languages
• Complete distributional problems, hard languages, and resource-bounded measure

This page was built for publication: Distributionally hard languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5945724)