From nobody Thu Nov  7 14:08 EST 1996
Date: Thu, 7 Nov 1996 14:07:54 -0500 (EST)
From: uid no body <nobody>
To: techreps@cs.buffalo.edu
Subject: techrep: POST request
Content-Type: text
Content-Length: 1759

Comments: hadar
ContactPerson: aduri@cs.buffalo.edu
Remote host: pollux.cs.buffalo.edu
Remote ident: aduri
### Begin Citation ### Do not delete this line ###
%R 96-21
%U /u0/csgrad/aduri/comp/mpap/nclose.ps
%A Belanger, Jay
%A Pavan, A.
%A Wang, Jie
%T Reductions Do Not Preserve Fast Convergence Rates in Average Time
%D November 07, 1996
%I Department of Computer Science, SUNY Buffalo
%X Cai and Selman proposed a general definition of average computation time
that, when applied to polynomials, results in a modification of Levin's
notion of average-polynomial-time.  The effect of the modification is to
control the rate of convergence of the expressions that define average
computation time.  With this modification, they proved a hierarchy theorem
for average-time complexity that is as tight as the Hartmanis-Stearns
hierarchy theorem for worst-case deterministic time.  They also proved that
under a fairly reasonable condition on distributions, called condition W, a
distributional problem is solvable in average-polynomial-time under the
modification exactly when it is solvable in average-polynomial-time under
Levin's definition.  Various notions of reductions, as defined by Levin and
others, play a central role in the study of average-case complexity.
However, the class of distributional problems that are solvable in
average-polynomial-time under the modification is not closed under the
standard reductions.  In particular, we prove that there is a distributional
problem that is not solvable in average-polynomial-time under the
modification but is reducible, by the identity function, to a distributional
problem that is, and whose distribution even satisfies condition W.