Сложность множеств, полученных как значения пропозициональных формул

Рассматривается интерпретация логических связок как операций на множествах двоичных слов; сложностью множества называется минимум колмогоровских сложностей его элементов. Легко проверить, что сложность множества, полученного применением логических операций, не превышает сложности конъюнкции их аргументов (с точностью до аддитивной константы). В работе доказано, что сложность полученного с помощью формулы $\Phi$ множества мала (ограничена константой), если $\Phi$ выводима в логике слабого исключенного третьего, и достигает указанной верхней оценки в противном случае.
Библиография: 7 названий.