From nobody@cse.Buffalo.EDU Thu Jul 1 10:21 EDT 1999 From: Nobody Date: Thu, 1 Jul 1999 10:21:33 -0400 (EDT) To: techreps@cse.Buffalo.EDU Subject: techrep: UPDATE request Content-Type: text Content-Length: 1693 ContactPerson: selman@cse.buffalo.edu Comments: file is readable on castor. Pavan discovered that the earlier entry linked to the wrong paper. This corrects it. Remote host: sargas.cse.buffalo.edu Remote ident: selman ### Begin Citation ### Do not delete this line ### %U /ftp/pub/WWW/faculty/selman/fps.ps %A Fortnow, L. %A Pavan, A. %A Selman, A. %T Distributionally-Hard Languages %R 99-02 %D April 26, 1999 %I Department of Computer Science and Engineering, SUNY Buffalo %K average-case complexity, P-bi-immune, P-printable, distributionally-hard %Y F.1.2;F.1.3 %X Define a set $L$ to be {\em distributionally-hard to recognize} if for every polynomial-time computable distribution $\mu$ with infinite support, $L$ is not recognizable in polynomial time on the $\mu$-average. Cai and Selman defined a modification of Levin's notion of average polynomial time and proved that every P-bi-immune language is distributionally-hard. Pavan and Selman proved that there exist distributionally-hard sets that are not P-bi-immune if and only P contains P-printable-immune sets. We extend this characterizion to include assertions about several traditional questions about immunity, about finding witnesses for NP-machines, and about existence of one-way functions. Similarly, we address the question of whether NP contains sets that are distributionally hard. Several of our results are implications for which we cannot prove whether or not their converse holds. In nearly all such cases we provide oracles relative to which the converse fails. We use the techniques of Kolmogorov complexity to describe our oracles and to simplify the technical arguments.