Random strings make hard instances
| Author(s) : | Pekka Orponen Harry Buhrman, |
| Publisher : | N/A |
| Publication Date : | 1994 |
| ISSN : | N/A |
| Abstract : | We establish the truth of the "instance complexity conjecture " in the case of DEXT-complete sets w.r.t. polynomial time computations, and r.e. complete sets w.r.t. recursive computations. Specifically, we obtain for every DEXT-complete set A an exponentially dense subset C such that for every nondecreasing polynomial t(n) =!(n log n), ic t, |