Hierarchies for semantic classes
We show that for any constant a, ZPP/b (n) strictly contains ZPTIME (na)/b (n) for some b (n)=
O (log n log log n). Our techniques are very general and give the same hierarchy for all …
O (log n log log n). Our techniques are very general and give the same hierarchy for all …
Randomness, provability, and the separation of Monte Carlo time and space
M Karpinski, R Verbeek - Computation Theory and Logic, 2005 - Springer
Separation theorems are essential in complexity theory: looking for strict lower and upper
bounds makes sense only in the context of a hierarchy theorem. For probabilistic complexity …
bounds makes sense only in the context of a hierarchy theorem. For probabilistic complexity …
A time lower bound for satisfiability
D Van Melkebeek, R Raz - Theoretical Computer Science, 2005 - Elsevier
We show that a deterministic Turing machine with one d-dimensional work tape and random
access to the input cannot solve satisfiability in time na for a<(d+ 2)/(d+ 1). For …
access to the input cannot solve satisfiability in time na for a<(d+ 2)/(d+ 1). For …
[PDF][PDF] Time hierarchies for computations with a bit of advice
K Pervyshev - … Colloquium on Computatioinal Complexity, TR05-054, 2005 - Citeseer
A polynomial time hierarchy for ZPTime with one bit of advice is proved. That is for any
constants a and b such that 1< a< b, ZPTime [na]/1⊊ ZPTime [nb]/1. The technique …
constants a and b such that 1< a< b, ZPTime [na]/1⊊ ZPTime [nb]/1. The technique …
Complexity: What, Why, and How
V Lakshmikantham, SK Sen - Mathematics in Science and Engineering, 2005 - Elsevier
The word “complexity” is the noun of the word “complex” which means, according to Collins
Gem English Dictionary, made up of parts, complicated. As a noun, complexity means whole …
Gem English Dictionary, made up of parts, complicated. As a noun, complexity means whole …
[PDF][PDF] Applications de la complexité de Kolmogorova la complexité classique et quantique
E Pascal, P KOIRAN, ENSL LIP - 2005 - irif.fr
La complexité du calcul se penche sur la question des ressources nécessaires (par
exemple, le temps, l'espace-mémoire, la quantité de communication) pour calculer des …
exemple, le temps, l'espace-mémoire, la quantité de communication) pour calculer des …