Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR02-014 | 28th March 2002 00:00


Revision #1
Authors: Philippe Moser
Accepted on: 28th March 2002 00:00
Downloads: 1412


We use Lutz's resource bounded measure theory to prove that, either \tbf{RP} is
small, or \tbf{ZPP} is hard.
More precisely, we prove that if \tbf{RP} has not p-measure zero, then
\tbf{ZPP} equals \tbf{EXP} on almost half the input lengths.
Second, we prove that that if \tbf{RP} has not p-measure zero, then for every $k \geq 1$,
\tbf{ZPP} is not included in $\mbf{DTIME}(2^{O(n^k)})$ for almost half the
input lengths $n$, i.e.
on almost half the input lengths
\tbf{ZPP} is hard.
Next, we prove that if \tbf{NP} has not p-measure zero, then derandomization of
\textbf{AM} is possible on almost half the input lengths, i.e.
$\mbf{NP} = \mbf{AM}$ on almost half the input lengths.
Finally, we prove easiness versus randomness tradeoffs for classes in the polynomial
time hierarchy.
We show that it appears to every strong adversary, that either,
every $\sig[i]$ algorithm can be simulated infinitely often by a subexponential
co-nondeterministic time algorithm, having oracle access to $\sig[i-2]$, or
$\sig[i] = \mbf{BP} \sig[i] $.


TR02-014 | 10th December 2001 00:00

Computational Complexity on Computable Metric Spaces

Authors: Klaus Weihrauch
Publication: 26th February 2002 10:27
Downloads: 1693


We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko \cite{Ko91} et al. Although this definition of ${\rm TIME}$ as the maximum of a generally infinite family of numbers looks straightforward, at first glance, examples for which this maximum exists seem to be very rare. It is the main purpose of this paper to prove that, nevertheless, the definition has a large number of important applications. Using the framework of TTE \cite{Wei00}, we introduce computable metric spaces and computability on the compact subsets. We prove that every computable metric space has a {\em c-proper} c-admissible representation. We prove that Turing machine time complexity of a function computable relative to c-admissible c-proper representations has a computable bound on every computable compact subset. We prove that computably compact computable metric spaces have {\em concise} c-proper c-admissible representations and show by examples that many canonical representations are of this kind. Finally, we compare our definition with a similar but not equivalent one by Labhalla et al. \cite{LLM01}. Several examples illustrate the concepts. By these results natural and realistic definitions of computational complexity are now available for a variety of numerical problems such as image processing, integration, continuous Fourier transform or wave propagation.

ISSN 1433-8092 | Imprint