bigpage.tex
\oddsidemargin  0.0in
\evensidemargin 0.0in
\textwidth      6.5in
\headheight     0.0in
\topmargin      -0.2in
\textheight 	8.7in


commands.tex
\usepackage{amsfonts}
\usepackage{amsmath} 
\usepackage{amssymb}
\usepackage{enumerate}

% Decision Problems 
%\newcommand{\SAT}{\mathrm{SAT}}
%\newcommand{\MAXSAT}{\mathrm{MAXSAT}}
%\newcommand{\MAXTSAT}{\mathrm{MAX3SAT}}
\newcommand{\MAXSAT}{\textsc{MaxSat}}
\newcommand{\MAXTSAT}{\textsc{Max3Sat}}
\newcommand{\SAT}{\textsc{Sat}}
\newcommand{\MAXCLIQUE}{\textsc{MaxClique}}
\newcommand{\CLIQUE}{\textsc{Clique}}

% Proof Commands
\newcommand{\PROOF}{\begin{proof}}%{{\noindent\bf{\em Proof:\/}~~}}
\newcommand{\PROOFSKETCH}{{\noindent\bf{\em Proof sketch:\/}~~}}
\newcommand{\QED}{\end{proof}}
\newcommand{\QEDbox}{\nolinebreak{\hfill $\square$}\vspace*{0.3cm}}

% Miscellaneous
\newcommand{\third}{3^{\mathrm{rd}}}
\newcommand{\second}{2^{\mathrm{nd}}}
\newcommand{\first}{1^{\mathrm{st}}}
\newcommand{\Prob}{\mathrm{Prob}}
\newcommand{\floor}[1]{ \left\lfloor #1 \right\rfloor }
\newcommand{\ceil}[1]{ \left\lceil #1 \right\rceil }
\newcommand{\range}{\mathrm{range}}
\newcommand{\myset}[2]{ \left\{ #1 \left| #2 \right. \right\} }
\newcommand{\mysetl}[2]{ \left\{\left. #1 \right| #2 \right\} }
\newcommand{\bval}[1]{[\![ #1 ]\!]}
\newcommand{\prefix}{\sqsubseteq}
\newcommand{\prprefix}{\underset{\neq}{\sqsubset}}
\newcommand{\st}{{\rm st}}
\newcommand{\diam}{\mathrm{diam}}
\newcommand{\doublespace}{\renewcommand{\baselinestretch}{1.5}\normalsize}
\newcommand{\binary}{\{0,1\}^*}
\newcommand{\limn}{\lim\limits_{n\to\infty}}
\newcommand{\liminfn}{\liminf\limits_{n\to\infty}}
\newcommand{\limsupn}{\limsup\limits_{n\to\infty}}
\newcommand{\ith}{{i^{\mathrm{th}}}}
\renewcommand{\Pr}[2]{\underset{#1}{\mathrm{Prob}}\left[#2\right]}
\newcommand{\size}[1]{\parallel\negthinspace #1\negthinspace\parallel}
%\newcommand{\restr}{\mbox{\raisebox{.5mm}{$\upharpoonright$}}}
\newcommand{\restr}{\upharpoonright}

% Blackboard Bold Sets
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}

% Measure and Dimension
\newcommand{\p}{{\mathrm{p}}}
\newcommand{\ptwo}{{\p_2}}
\newcommand{\pspace}{{\mathrm{pspace}}}
\newcommand{\ptwospace}{{\mathrm{p}_2\mathrm{space}}}
\newcommand{\poly}{{\mathrm{poly}}}
\newcommand{\rec}{{\mathrm{rec}}}
\newcommand{\all}{{\mathrm{all}}}
\newcommand{\FS}{{\mathrm{FS}}}
\newcommand{\comp}{{\mathrm{comp}}}
\newcommand{\constr}{{\mathrm{constr}}}
\newcommand{\mup}{\mu_{\mathrm{p}}}
\newcommand{\dimall}{\dim_\all}
\newcommand{\dimp}{\dim_\p}
\newcommand{\dimfs}{\mathrm{dim}_\mathrm{FS}}
\newcommand{\dimpspace}{\mathrm{dim}_\mathrm{pspace}}
\newcommand{\dimh}{\mathrm{dim}_\mathrm{H}}
\newcommand{\dimrec}{\mathrm{dim}_\mathrm{rec}}
\newcommand{\dimcomp}{\mathrm{dim}_\comp}
\newcommand{\cdim}{\mathrm{cdim}}
\newcommand{\dimptwo}{\dim_\ptwo}
\newcommand{\dimptwospace}{\dim_\ptwospace}
\newcommand{\muptwo}{\mu_\ptwo}

\renewcommand{\dim}{{\mathrm{dim}}}
\newcommand{\udim}{{\overline{\dim}}}
\newcommand{\ldim}{{\underline{\dim}}}
\newcommand{\dimpack}{{\dim}_{\mathrm{P}}}
\newcommand{\dimb}{{\dim}_{\mathrm{B}}}
\newcommand{\udimb}{{\udim}_{\mathrm{B}}}
\newcommand{\ldimb}{{\ldim}_{\mathrm{B}}}
\newcommand{\udimmb}{\udim_{\mathrm{MB}}}

\newcommand{\Dim}{{\mathrm{Dim}}}
\newcommand{\cDim}{{\mathrm{cDim}}}
\newcommand{\Dimfs}{{\Dim_\FS}}
\newcommand{\Dimp}{{\Dim_\p}}
\newcommand{\Dimcomp}{{\Dim_\comp}}

\newcommand{\str}{{\mathrm{str}}}
\newcommand{\regSS}{S^\infty}
\newcommand{\strSS}{S^\infty_{\mathrm{str}}}

\newcommand{\G}{{\mathcal{G}}}
\newcommand{\Ghat}{{\widehat{\G}}}
\newcommand{\hatG}{\Ghat}
\newcommand{\Gstr}{\G^{\mathrm{str}}}
\newcommand{\hatGstr}{\hatG^{\mathrm{str}}}

\newcommand{\D}{{\mathcal{D}}}
\newcommand{\Gconstr}{\mathcal{G}_\mathrm{constr}}

\newcommand{\C}{\mathbf{C}}
\newcommand{\bd}{{\mathbf{d}}}
\newcommand{\FREQ}{{\mathrm{FREQ}}}
\newcommand{\freq}{{\mathrm{freq}}}

% Prediction
\newcommand{\pred}{\mathrm{pred}}
\newcommand{\Pred}{\mathrm{Pred}}
\newcommand{\Predp}{\mathrm{Pred}_\p}
\newcommand{\predp}{\mathrm{pred}_\p}
\newcommand{\unpred}{\mathrm{unpred}}
\newcommand{\unpredlog}{\mathrm{unpred}^\mathrm{log}}
\newcommand{\unpredlogp}{\mathrm{unpred}^\mathrm{log}_\mathrm{p}}
\newcommand{\unpredabs}{\mathrm{unpred}^\mathrm{abs}}
\newcommand{\unpredabsp}{\mathrm{unpred}^\mathrm{abs}_\mathrm{p}}
\newcommand{\predcomp}{\pred_\comp}
\newcommand{\predfs}{\pred_\mathrm{FS}}
\newcommand{\Ik}{{\cal I}_k}
\newcommand{\Ikbar}{\overline{\Ik}}
\newcommand{\Hk}{{\cal H}_k}

\newcommand{\calL}{{\mathcal{L}}}
\newcommand{\logL}{\calL^{\log}}
\newcommand{\strlogL}{\calL^{\log}_{\str}}
\newcommand{\abs}{\mathrm{abs}}
\newcommand{\absL}{\calL^{\abs}}

\newcommand{\loss}{{\mathit{loss}}}
\newcommand{\losslog}{\loss^{\log}}
\newcommand{\lossabs}{\loss^\abs}


% Complexity Classes
\newcommand{\co}[1]{\mathrm{co}-#1}
\newcommand{\strings}{\{0,1\}^*}
\newcommand{\ALL}{\mathrm{ALL}}
\newcommand{\RAND}{\mathrm{RAND}}
\newcommand{\DIM}{\mathrm{DIM}}
\newcommand{\DIMstr}{\DIM_\str}
\newcommand{\coDIM}{\mathrm{coDIM}}
\newcommand{\REC}{\mathrm{REC}}
\newcommand{\DEC}{\mathrm{DEC}}
\newcommand{\CE}{\mathrm{CE}}
\newcommand{\coCE}{\mathrm{coCE}}
\newcommand{\RE}{\mathrm{RE}}
\newcommand{\coRE}{\mathrm{coRE}}
\newcommand{\SPARSE}{\mathrm{SPARSE}}
\newcommand{\DENSE}{\mathrm{DENSE}}
\newcommand{\DENSEio}{\mathrm{DENSE}_\mathrm{i.o.}}
\newcommand{\DTIME}{\mathrm{DTIME}}
\newcommand{\DTIMEF}{\mathrm{DTIMEF}}
\newcommand{\NP}{{\ensuremath{\mathrm{NP}}}} 
\newcommand{\coNP}{\co{\NP}}
\newcommand{\DeltaPTwo}{\Delta^{\mathrm{P}}_2}
\newcommand{\DP}{\mathrm{DP}}
\newcommand{\SUBEXP}{\mathrm{SUBEXP}}
\newcommand{\SIZE}{{\rm SIZE}}
\newcommand{\BPP}{{\rm BPP}}
\newcommand{\ZPP}{{\rm ZPP}}
\newcommand{\RP}{{\rm RP}}
\newcommand{\coRP}{\co{\RP}}
\newcommand{\E}{{\rm E}}
\newcommand{\EE}{{\rm EE}}
\newcommand{\ESPACE}{{\rm ESPACE}}
\newcommand{\PSPACE}{{\rm PSPACE}}
\renewcommand{\P}{\ensuremath{{\mathrm P}}}
\newcommand{\Etwo}{{\rm E_2}}
\newcommand{\EXP}{{\rm EXP}}
\newcommand{\DSPACE}{{\rm DSPACE}}
\newcommand{\NE}{{\rm NE}}
\newcommand{\NEE}{{\rm NEE}}
\newcommand{\Poly}{{\rm P}}
\newcommand{\Pc}{{\rm P}}
\newcommand{\PPoly}{{\rm {P/Poly}}}
\newcommand{\Psel}{{\rm {P-sel}}}
\newcommand{\WS}{{\rm WS}}
\newcommand{\Ei}{\E_i}
\newcommand{\EiSPACE}{\mathrm{E}_i\mathrm{SPACE}}
\newcommand{\EoneSPACE}{\mathrm{E}_1\mathrm{SPACE}}
\newcommand{\linear}{\mathrm{linear}}
\newcommand{\polynomial}{\mathrm{polynomial}}
\newcommand{\EXPSPACE}{\mathrm{EXPSPACE}}

% Calligraphy
\newcommand{\calA}{{\cal A}}
\newcommand{\calB}{{\cal B}}
\newcommand{\calC}{{\cal C}}
\newcommand{\calD}{{\cal D}}
\newcommand{\F}{{\mathcal{F}}}
\newcommand{\calH}{{\cal H}}
\newcommand{\calP}{{\cal P}}

% Kolmogorov Complexity
\newcommand{\calKS}{{\cal KS}}
\newcommand{\calKT}{{\cal KT}}
\newcommand{\calK}{{\cal K}}
\newcommand{\calCD}{{\cal CD}}
\newcommand{\calCND}{{\cal CND}}
\newcommand{\K}{{\mathrm{K}}}
\newcommand{\KS}{{\mathrm{KS}} }
\newcommand{\KT}{{\mathrm{KT}} }
\newcommand{\CD}{{\mathrm{CD}} }
\newcommand{\CND}{{\mathrm{CND}} }

% Reductions
\newcommand{\leqpm}{\leq^\p_\mathrm{m}}
\newcommand{\leqmp}{\leqpm}
\newcommand{\leqpT}{\leq^\mathrm{p}_\mathrm{T}}
\newcommand{\leqpr}{\leq^\mathrm{p}_r}
\newcommand{\leqonettp}{\leq_{1-\mathrm{tt}}^{\mathrm{P}}}
\newcommand{\murec}[1]{{\mu({#1}\mid \REC)}}
\newcommand{\muex}[1]{{\mu({#1}\mid \Etwo)}}
\newcommand{\redu}[2]{{\leq^{\rm {{#1}}}_{{\rm{#2}}}}}
\newcommand{\predu}[1]{{\redu{P}{#1}}}
\newcommand{\pmred}{{\predu{m}}}
\newcommand{\ptred}{{\predu{T}}}
% Reduction Closures
\newcommand{\Pm}{\mathrm{P}_{\mathrm{m}}}
\newcommand{\Ponett}{\mathrm{P}_{1-\mathrm{tt}}}
\newcommand{\Pmi}{\Pm^{-1}}
\renewcommand{\Pr}{\mathrm{P}_r}
\newcommand{\Pri}{\Pr^{-1}}
% Degrees
\newcommand{\degpm}{\mathrm{deg}^{\mathrm{p}}_{\mathrm{m}}}
\newcommand{\degpr}{\mathrm{deg}^\mathrm{p}_r}
\newcommand{\equivpm}{\equiv^\p_\mathrm{m}}
% Hard and Complete sets
\newcommand{\m}{\mathrm{m}}
\newcommand{\Cpm}{\calC^\p_\m}
\newcommand{\Hpm}{\calH^\p_\m}
\newcommand{\Cpr}{\calC^\p_r}
\newcommand{\Hpr}{\calH^\p_r}



% Names
\newcommand{\MartinLof}{Martin-L\"{o}f}

\newcommand{\nth}{n^{\mathrm{th}}}
numbering.tex
\usepackage{amsthm}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem*{claim}{Claim}

\newenvironment{theorem_cite}[1]
{\begin{theorem}  {\rm (#1)}}
{\end{theorem}}
\newenvironment{lemma_cite}[1]
{\begin{lemma}  {\rm (#1)}}
{\end{lemma}}
\newenvironment{corollary_cite}[1]
{\begin{corollary}  {\rm (#1)}}
{\end{corollary}}
\newenvironment{proposition_cite}[1]
{\begin{proposition}  {\rm (#1)}}
{\end{proposition}}

\newenvironment{theorem_named}[1]
{\begin{theorem} {\rm (#1)}}
{\end{theorem}}
\newenvironment{lemma_named}[1]
{\begin{lemma} {\rm (#1)}}
{\end{lemma}}

\newenvironment{proof_claim}
{\noindent{\em Proof of Claim.}}
{\hfill $\square$ {\em Claim.}}

\newenvironment{Proof}
{\begin{proof}}
{\end{proof}}

\newenvironment{pf}
{\begin{proof}[Pf.]}
{\end{proof}}

\newtheorem{observation}[theorem]{Observation}
\newtheorem{observations}[theorem]{Observations}

\newtheorem{openproblem}[theorem]{Open Problem}
\newtheorem{openquestion}[theorem]{Open Question}

\newtheorem{fact}[theorem]{Fact}
\newtheorem{facts}[theorem]{Facts}

\newtheorem{problem}[theorem]{Problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem*{definition}{Definition}
\newtheorem*{defn}{Definition}
\newtheorem*{definitions}{Definitions}

\theoremstyle{definition}

\newtheorem{example}[theorem]{Example}
\newtheorem{examples}[theorem]{Examples}
\newtheorem*{example*}{Example}
\newtheorem*{examples*}{Examples}

\newenvironment{example_cite}[1]
{\begin{example}  {\rm (#1)}}
{\end{example}}

\newtheorem{construction}[theorem]{Construction}
\newtheorem{extension}[theorem]{Extension}

\newtheorem*{remarks}{Remarks}
\newtheorem*{remark}{Remark}

\newtheorem*{notation}{Notation}
\newtheorem*{terminology}{Terminology}

\newtheorem*{ack}{Acknowledgment}
\newtheorem*{acks}{Acknowledgments}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\theoremstyle{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\numberwithin{equation}{section}
\numberwithin{figure}{section}

prelim.tex
\section{Preliminaries}\label{sec:prelim}

The set of all finite binary strings is $\{0,1\}^*$.  The empty string
is denoted by $\lambda$ and $\{0,1\}^+ = \{0,1\}^* - \{\lambda\}$.  We
use the standard enumeration of binary strings $s_0 = \lambda, s_1 =
0, s_2 = 1, s_3 = 00, \ldots$. The length of a string $x\in\strings$
is denoted by $|x|$.  We use the notation $\{0,1\}^{\leq n} = \{x \in
\{0,1\}^* \mid |x| \leq n\}$ and $\{0,1\}^{> n} = \{x \in \{0,1\}^*
\mid |x| > n\}$.

All {\em languages} (decision problems) in this paper are encoded as
subsets of $\{0,1\}^*$.  For a language $A \subseteq \strings$, we
define $A_{\leq n} = \{ x \in A \big| |x| \leq n \}$.  We routinely
identify $A$ with its infinite binary characteristic sequence
according to the standard enumeration of binary strings.  We write
$A\restr n$ for the $n$-bit prefix of the characteristic sequence of
$A$, and $A[n]$ for the $\nth$-bit of its characteristic sequence.

Let $\leqpr$ be a reducibility.  For any $A \subseteq \{0,1\}^*$, let
$$\Pr(A) = \{ B \subseteq \{0,1\}^* \mid B \leqpr A \}$$ be the {\em
$\leqpr$-lower span of $A$}, $$\Pri(A) = \{ B \subseteq \{0,1\}^* \mid
A \leqpr B \}$$ be the {\em $\leqpr$-upper span of $A$}, and
$$\degpr(A) = \Pr(A) \cap \Pri(A)$$ be the {\em $\leqpr$-degree of
$A$}.  For any complexity class $\calD$, the class of {\em $\leqpr$-hard
languages for $\calD$} is
$$\Hpr(\calD) = \{ A \subseteq \{0,1\}^* \mid \calD \subseteq \Pr(A)
\},$$
and the class of {\em $\leqpr$-complete languages for $\calD$} is
$$\Cpr(\calD) = \calD \cap \Hpr(\calD).$$

Let $\mathrm{resource} \in \{\mathrm{time},\mathrm{space}\}$ and let
  $t(n)$ be a resource bound.  Let $l \in \N$.  A function $f: \N^l
  \times \{0,1\}^* \to [0,\infty) \cap \Q$ is {\em $t(n)$-resource
  exactly computable} if there is a Turing machine that computes
  $f(k_1,\ldots,k_l,w)$ using at most $t(k_1+\cdots+k_l+|w|)$ resource
  for all $(k_1,\ldots,k_l,w) \in \N^l \times \{0,1\}^*$.  Let $g :
  \N^l \times \{0,1\}^* \to [0,\infty)$ be a real-valued function.  An
  {\em approximation} of $g$ is a function $\hat{g} : \N^{l+1} \times
  \{0,1\}^* \to [0,\infty)$ such that
$$|g(x) - \hat{g}(r,x)| \leq 2^{-r}$$ for all $x\in \N^l \times
\{0,1\}^*$ and $r\in\N$.  We say that $g$ is {\em $t(n)$-resource
computable} if there is an exactly $t(n)$-resource computable
approximation $\hat{g}$ of $g$.  A family of functions $(f_i : \N^l
\times \{0,1\}^* \to [0,\infty) \mid i \in \N)$ is {\em uniformly $t(n)$-resource
(exactly) computable} if the function $f(i,x) = f_i(x)$ is
$t(n)$-resource (exactly) computable.

A function $f$ is {\em $\p$-computable} (respectively, {\em
  $\pspace$-computable}) if it is $O(n^k)$-time (respectively,
  $O(n^k)$-space) computable for some $k \in \N$, and $f$ is {\em
  $\ptwo$-computable} (respectively, {\em $\ptwospace$-computable}) if
  it is $O(2^{(\log n)^k})$-time (respectively, $O(2^{(\log
  n)^k})$-space) computable for some $k \in \N$.  Throughout this
  paper, unless otherwise specified, $\Delta$ denotes any of the {\em
  resource bounds} $\p$, $\ptwo$, $\pspace$, or $\ptwospace$.  The
  concept of an {\em exactly $\Delta$-computable} function is defined
  analogously.

sssd.bbl
\begin{thebibliography}{10}

\bibitem{AmMaZh96}
K.~Am{bos-Spies}, E.~Mayordomo, and X.~Zheng.
\newblock A comparison of weak completeness notions.
\newblock In {\em Proceedings of the Eleventh {IEEE} Conference on
  Computational Complexity}, pages 171--178, 1996.

\bibitem{AmMeReSt01}
K.~Ambos-Spies, W.~Merkle, J.~Reimann, and F.~Stephan.
\newblock Hausdorff dimension in exponential time.
\newblock In {\em Proceedings of the 16th IEEE Conference on Computational
  Complexity}, pages 210--217, 2001.

\bibitem{AmNeTe96}
K.~Amb{os-Spies}, H.-C. Neis, and S.~A. Terwijn.
\newblock Genericity and measure for exponential time.
\newblock {\em Theoretical Computer Science}, 168:3--19, 1996.

\bibitem{BennettGill81}
C.~H. Bennett and J.~Gill.
\newblock Relative to a random oracle {$A$, ${\rm P}^A \neq {\rm NP}^A \neq
  \mbox{co-NP}^A$} with probability 1.
\newblock {\em SIAM Journal on Computing}, 10:96--113, 1981.

\bibitem{Book74}
R.~V. Book.
\newblock Comparing complexity classes.
\newblock {\em Journal of Computer and System Sciences}, 9:213--229, 1974.

\bibitem{BuhvMe98}
H.~Buhrman and D.~{van Melkebeek}.
\newblock Hard sets are hard to find.
\newblock {\em Journal of Computer and System Sciences}, 59:327--345, 1999.

\bibitem{Haus19}
F.~Hausdorff.
\newblock Dimension und {\"a}usseres {M}ass.
\newblock {\em Mathematische Annalen}, 79:157--179, 1919.

\bibitem{Hitchcock:FDLLU}
J.~M. Hitchcock.
\newblock Fractal dimension and logarithmic loss unpredictability.
\newblock {\em Theoretical Computer Science}.
\newblock To appear.

\bibitem{Hitchcock:SDNC}
J.~M. Hitchcock, J.~H. Lutz, and E.~Mayordomo.
\newblock Scaled dimension and nonuniform complexity.
\newblock {\em Journal of Computer and System Sciences}.
\newblock To appear.

\bibitem{Lutz:CDHP}
D.~W. Juedes and J.~H. Lutz.
\newblock The complexity and distribution of hard problems.
\newblock {\em SIAM Journal on Computing}, 24(2):279--295, 1995.

\bibitem{Lind93}
W.~Lindner.
\newblock On the polynomial time bounded measure of one-truth-table degrees and
  p-selectivity, 1993.
\newblock Diplomarbeit, Technische {Universit{\"{a}}t} Berlin.

\bibitem{Lutz:DCC}
J.~H. Lutz.
\newblock Dimension in complexity classes.
\newblock {\em SIAM Journal on Computing}.
\newblock To appear. Available as Technical Report cs.CC/0203016, Computing
  Research Repository, 2002.

\bibitem{Lutz:UMST}
J.~H. Lutz.
\newblock An upward measure separation theorem.
\newblock {\em Theoretical Computer Science}, 81:127--135, 1991.

\bibitem{Lutz:AEHNC}
J.~H. Lutz.
\newblock Almost everywhere high nonuniform complexity.
\newblock {\em Journal of Computer and System Sciences}, 44:220--258, 1992.

\bibitem{Lutz:SST}
J.~H. Lutz.
\newblock A small span theorem for {P/Poly-Turing} reductions.
\newblock In {\em Proceedings of the Tenth Annual Structure in Complexity
  Theory Conference}, pages 324--330, 1995.

\bibitem{Lutz:MSDHL}
J.~H. Lutz and E.~Mayordomo.
\newblock Measure, stochasticity, and the density of hard languages.
\newblock {\em SIAM Journal on Computing}, 23:762--779, 1994.

\bibitem{Lutz:CVKL}
J.~H. Lutz and E.~Mayordomo.
\newblock Cook versus {Karp-Levin}: Separating completeness notions if {NP} is
  not small.
\newblock {\em Theoretical Computer Science}, 164:141--163, 1996.

\bibitem{Mayo94}
E.~Mayordomo.
\newblock Almost every set in exponential time is {P}-bi-immune.
\newblock {\em Theoretical Computer Science}, 136(2):487--506, 1994.

\bibitem{NisWig94}
N.~Nisan and A.~Wigderson.
\newblock Hardness vs randomness.
\newblock {\em Journal of Computer and System Sciences}, 49:149--167, 1994.

\end{thebibliography}
