Some Observations about the Randomness of Hard Problems
Dung T. Huynh · SIAM Journal on Computing · 1986
In this note we investigate some connections between hard languages and random languages. We show that there exist languages that are both hard and random. We also show that every EXPTIME-hard language is polynomial-time weakly random.