Some Observations about the Randomness of Hard Problems
From MaRDI portal
Publication:3756525
DOI10.1137/0215079zbMath0619.68046OpenAlexW1992643817MaRDI QIDQ3756525
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
Related Items
On solving hard problems by polynomial-size circuits, Random languages for nonuniform complexity classes, Nonuniform complexity and the randomness of certain complete languages, Weak completeness in \(\text{E}\) and \(\text{E}_{2}\), Almost everywhere high nonuniform complexity