RefDoc
Haut

Faire une nouvelle recherche
Make a new search
Lancer la recherche


Titre du document / Document title

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

Auteur(s) / Author(s)

FORTNOW Lance (1) ; HITCHCOCK John M. (2) ; PAVAN A. (3) ; VINUDCHANDRAN N. V. (4) ; FENGMING WANG (3) ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

(1) Department of Computer Science, University of Chicago, ETATS-UNIS
(2) Department of Computer Science, University of Wyoming, ETATS-UNIS
(3) Department of Computer Science, Iowa State University, ETATS-UNIS
(4) Department of Computer Science and Engineering, University of Nebraska-Lincoln, ETATS-UNIS

Résumé / Abstract

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.

Revue / Journal Title

Lecture notes in computer science    ISSN  0302-9743 

Source / Source

Congrès
Automata, languages and programming :   ( Part I-II : 33rd international colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006 : proceedings )
International Colloquium on Automata, Languages, and Programming No33, Venice , ITALIE (2006)
2006  , vol. 4052, pp. 335-345[Note(s) : 2 vol.(729, 603 p.), ] [Document : 11 p.] (22 ref.) ISBN 3-540-35904-4 ; 3-540-35907-9 ;

Langue / Language

Anglais

Editeur / Publisher

Springer, Berlin, ALLEMAGNE  (1973) (Revue)
Springer, Berlin, ALLEMAGNE  ETATS-UNIS  (2006) (Monographie)

Mots-clés anglais / English Keywords

Kolmogorov equation

;

Space complexity

;

Zero one law

;

Character string

;

Mots-clés français / French Keywords

.

;

Equation Kolmogorov

;

Complexité espace

;

Loi zéro un

;

Chaîne caractère

;

Mots-clés espagnols / Spanish Keywords

Ecuación Kolmogorov

;

Complejidad espacio

;

Ley cero uno

;

Cadena carácter

;

Localisation / Location

INIST-CNRS, Cote INIST : 16343, 35400017280968.0290

Nº notice refdoc (ud4) : 19993435



Faire une nouvelle recherche
Make a new search
Lancer la recherche
Bas