ContactPerson: aduri@cse.buffalo.edu
### Begin Citation ### Do not delete this line ###
%R 2001-10
%U /home/csgrad/aduri/comp/thesis/thesis.ps
%A Pavan, A.
%T Average-case complexity theory and polynomial-time reductions
%D August 26, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K average-case complexity, reasonable distributions, distributionally-hard languages, polynomial-time reducibilities, separating NP-completeness notions
%X This thesis studies average-case complexity 
theory and polynomial-time reducibilities. The issues in average-case 
complexity arise primarily from Cai and Selman's extension of Levin's 
definition of average polynomial time. We study polynomial-time 
reductions between distributional problems. Under strong but 
reasonable hypotheses we separate ordinary $\NP$-completeness notions.   
The average-case complexity of a problem is, in many cases, a more 
significant measure than the worst-case complexity. 
It is known that some $\NP$-complete problems, such as $k$-coloring and 
Hamiltonian cycle, can be solved quickly on average. 
This has motivated 
the development of the study of average-case analysis of algorithms. 
Levin~\cite{Levin86} initiated a general study of average-case complexity by 
defining a robust notion of average polynomial time and the notion of 
distributional $\NP$-completeness. 
Cai and Selman ~\cite{CaiSelman99} gave a general definition of {\em $T$ on aver 
age} for arbitrary 
time bounds $T$. They observed difficulties with Levin's definition of 
average polynomial time when applied to unreasonable input distributions. 
Their definition of average polynomial time slightly modifies Levin's 
definition to avoid these difficulties. 
In this thesis we study reasonable distributions, 
distributionally-hard languages, and reductions among distributional 
problems.   
We prove several results demonstrating that it suffices to restrict 
one's attention to reasonable distributions. 
This is important because both Levin's definition and 
Cai and Selman's definition yield unsatisfactory consequences when we 
permit unreasonable distributions. We show that if $\NP$ has a 
$\DTIME(2^n)$-bi-immune language, then every $\DistNP$-complete problem must 
have a 
reasonable distribution. We prove that the class $\ppcomp$, the set of languages 
that can be decided in average polynomial time with respect to every 
polynomial-time computable distribution, remains 
unchanged when restricted to reasonable distributions. We strengthen and 
present a simpler proof of a 
result of Belanger and Wang~\cite{BelangerWang96}, which shows that Cai and Selm 
an's definition of 
average-polynomial time is not closed under many-one reductions.   
Cai and Selman showed 
that every is $\P$-bi-immune language is dis\-tri\-bu\-tionally-hard. We study 
the question of whether there exist distributionally-hard languages that are not 
$\P$-bi-immune. First we show that such languages exist if and only if $\P$ 
contains $\P$-printable-immune sets. Then we extend this characterization 
significantly to include assertions about several traditional 
questions about immunity, about finding witnesses for $\NP$-machines, and 
about the existence of one-way functions.   
Next we study polynomial-time reducibilities. 
Ladner, Lynch, and Selman~\cite{LadnerLynchSelman75} 
showed, in the context of worst-case complexity, that various poly\-no\-mi\-al-t 
ime 
reductions differ in $\E$. We show similar results 
for reductions between distributional problems and we show that 
most of the completeness notions for $\DistEXP$ are 
different.   
Finally, we turn our attention to the question 
of whether various notions of 
$\NP$-completeness are different. Lutz and Mayordomo, under the 
hypothesis that the $p$-measure of $\NP$ is not zero, and Ambos-Spies and 
Bentzien, under the hypothesis that $\NP$ has a $p$-generic language, 
showed that various completeness notions in $\NP$ are different. 
We introduce a structural hypothesis not involving stochastic properties 
and prove that the existence of a Turing complete language for $\NP$ 
that is not truth-table complete follows from our hypothesis. 
This result is the first to provide evidence that truth-table 
completeness for $\NP$ is weaker than Turing completeness for $\NP$.