ECCC-Report TR02-014https://eccc.weizmann.ac.il/report/2002/014Comments and Revisions published for TR02-014en-usThu, 28 Mar 2002 00:00:00 +0200
Revision 1
| |
Philippe Moser
https://eccc.weizmann.ac.il/report/2002/014#revision1 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] $.
Thu, 28 Mar 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2002/014#revision1
Paper TR02-014
| Computational Complexity on Computable Metric Spaces |
Klaus Weihrauch
https://eccc.weizmann.ac.il/report/2002/014We 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.
Tue, 26 Feb 2002 10:27:21 +0200https://eccc.weizmann.ac.il/report/2002/014