Some Observations about the Randomness of Hard Problems

DOI10.1137/0215079MaRDI QIDQ3756525zbMATH OpenOpenAlexFDO

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

EXPTIME-hard languagehard languageshardnessimmunityrandom languagesrandomness

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

(8)

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

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)