Détail de la notice
Titre du Document
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
ICALP 2006
Auteur(s)
FORTNOW Lance ; HITCHCOCK John M. ; PAVAN A. ; ...
Résumé
We apply recent results on extracting randomness from independent sources to ''extract Kolmogorov complexity. For any a, ∈> 0, given a string x with K(x) > α|x|, we show how to use a constant number of advice bits to efficiently compute another string y, |y| = Ω|x|), with K(y) > (1 - ∈)|y|. This result holds for both classical and space-bounded Kolmogorov complexity. We use the extraction procedure for space-bounded complexity to establish zero-one laws for polynomial-space strong dimension. Our results include: (i) If Dimpspace(E) > 0, then Dimpspace(E/O(1)) =1. (ii) Dini(E/O(1) |ESPACE) is either 0 or 1. (iii) Dim(E/poly | ESPACE) is either 0 or 1. In other words, from a dimension standpoint and with respect to a small amount of advice, the exponential-time class E is either minimally complex or maximally complex within ESPACE.
Editeur
Springer; Springer
Type du document
Conférence : International Colloquium on Automata, Languages, and Programming, 33, Venice, ITA, 2006
Identifiant
ISSN : 0302-9743 ISBN : 3-540-35904-4
Source
Lecture notes in computer science A. 2006, vol. 4052, pp. 335-345 [11 pages] [bibl. : 22 ref.]
Langue
Anglais
Pour les membres de la communauté du CNRS, ce document est autorisé à la reproduction à titre gratuit.
Pour les membres des communautés hors CNRS, la reproduction de ce document à titre onéreux sera fournie sous réserve d’autorisation du Centre Français d’exploitation du droit de Copie.

Pour bénéficier de nos services (strictement destinés aux membres de la communauté CNRS (Centre National de la Recherche Scientifique), de l'ESR français (Enseignement Supérieur et Recherche), et du secteur public français & étranger) :