Алгоритмические свойства линейно аппроксимируемых квазинормальных модальных логик

Исследуется вопрос о взаимосвязи между вычислительной сложностью проблемы разрешения модальной пропозициональной логики и сложностью контрмоделей для формул, которые ей не принадлежат. Известно, что для многих нормальных мономодальных пропозициональных логик разные исследователи применяли сходные конструкции для доказательства PSPACE-трудности проблемы разрешения логики и для обоснования нижних экспоненциальных оценок минимального числа элементов в шкалах Крипке, опровергающих формулы, не принадлежащие ей. Аналогичная ситуация наблюдается и для суперинтуиционистских пропозициональных логик. При этом какие-либо точно сформулированные математические критерии, выражающие эту наблюдаемую связь, автору неизвестны. В работе показано, что если отказаться от условия нормальности в модальных логиках, то можно найти контрпример. Именно, в работе строятся квазинормальные модальные пропозициональные логики, являющиеся линейно аппроксимируемыми и имеющие как сколь угодно высокую сложность проблемы разрешения, так и сколь угодно высокую степень неразрешимости, причём в обоих случаях достаточно рассматривать лишь константные фрагменты.