Финитные задачи и логика слабого закона исключенного третьего

Определяется новая характеристика пропозициональной формулы как операции над финитными задачами – мощность достаточного множества решений (ДМР). Доказывается, что если формула выводима в логике слабого закона исключенного третьего, то мощность ДМР ограничена константой, зависящей только от числа переменных; в противном случае достижимая мощность ДМР близка (больше корня некоторой степени) к тривиальной верхней оценке на нее. Это утверждение является аналогом ранее опубликованного результата автора об алгоритмической сложности множеств, полученных как значения пропозициональных формул. Также введено понятие колмогоровской сложности финитной задачи и получены аналогичные результаты.
Библиография: 11 названий.