3
Od ekstraktorów do generatorów pseudolosowych?
Luca Trevisan pokazał, ile konstrukcji generatorów pseudolosowych można uznać za konstrukcje ekstraktorów: http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf Czy istnieje sensowna rozmowa? Tj. Czy „naturalne” konstrukcje ekstraktorów można traktować jako konstrukcje pseudolosowych generatorów (PRG)? Konstrukcje ekstraktorów wydają się odpowiadać rozkładom na PRG (tak, że żadnemu wyróżniającemu nie uda się rozróżnić dla prawie wszystkich z nich). …