Aleksandr Viktorovich Chashkin

О сложности нумераторов в булевом кубе

Показано, что для произвольного множества $D\in\{0,1\}^n$ существует инъективная на этом множестве функция, которая нумерует наборы из $D$ целыми числами от нуля до $|D|-1$ и сложность которой по порядку величины не превосходит $|D|/\log_2|D|$. Установлено, что эта оценка минимальна с точностью до постоянного множителя...