Some Observations about the Randomness of Hard Problems

DOI10.1137/0215079zbMATH Open0619.68046OpenAlexW1992643817MaRDI QIDQ3756525FDOQ3756525

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

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

zbMATH Keywords

hardnessrandomnessimmunityrandom languageshard languagesEXPTIME-hard language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (7)

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

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)