Some Observations about the Randomness of Hard Problems

DOI10.1137/0215079zbMATHOpenAlexMaRDI QIDQ3756525FDO

Authors Dung T. Huynh

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0215079

zbMATH Keywords

hardnessrandomnessimmunityrandom languageshard languagesEXPTIME-hard language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3988704
• scientific article; zbMATH DE number 1555920
• On random hard sets for NP
• scientific article; zbMATH DE number 512813
• Nonuniform complexity and the randomness of certain complete languages

Cited in

(7)

• Properties of uniformly hard languages
• Almost everywhere high nonuniform complexity
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Random languages for nonuniform complexity classes
• The Complexity and Distribution of Hard Problems
• On solving hard problems by polynomial-size circuits
• Nonuniform complexity and the randomness of certain complete languages

This page was built for publication: Some Observations about the Randomness of Hard Problems

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