Some Observations about the Randomness of Hard Problems

This publication has 8 references indexed in Scilit:

• Bi-immune sets for complexity classes
  Theory of Computing Systems, 1985
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
  SIAM Journal on Computing, 1983
• Remarks on the complexity of an invariant of context-free grammars
  Acta Informatica, 1982
• Eine Neue invariante für kontextfreie sprachen
  Theoretical Computer Science, 1980
• On Isomorphisms and Density of $NP$ and Other Complete Sets
  SIAM Journal on Computing, 1977
• COMPUTATIONALLY COMPLEX AND PSEUDO-RANDOM ZERO-ONE VALUED FUNCTIONS††Portions of this work were carried out at Carngie-Mellon University, while the authors were in the Department of Computer Science. Portions of these results were reported in preliminary form in [1].
  Published by Elsevier ,1971
• Random Sets in Subrecursive Hierarchies
  Journal of the ACM, 1969
• On the concept of a random sequence
  Bulletin of the American Mathematical Society, 1940