Пусть у нас есть множество A, которое состоит из m целых чисел от 1 до n (будем считать, что , например, что m = n^o(1)). Мы хотим построить структуру данных, которая по числу будет определять, лежит ли оно в A. При этом, у нас будет жесткое ограничение: на каждый запрос алгоритм должен смотреть лишь на один бит структуры.

Какого минимального размера структуры можно достичь:

1. если алгоритм должен всегда выдавать верный ответ,

2. если алгоритм может ошибаться с вероятностью 1 процент (но при этом должен выдавать верный ответ с вероятностью 99 процентов для любого запроса)?