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

М. Н. Рыбаков

doi:10.26456/vtpmk520

Публикации

?

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

Вестник Тверского государственного университета. Серия: Прикладная математика. 2018. № 4. С. 87–97.

Рыбаков М. Н.

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

Научное направление: Математика

Приоритетные направления: компьютерно-математическое математика

Язык: русский

DOI

Текст на другом сайте

Ключевые слова: вычислительная сложность разрешимость семантика Крипке квазинормальная логика

On Undecidability Degree of Theory of Figures in Countable and Uncountable Linear Spaces

Дудаков С. М., Lobachevskii Journal of Mathematics 2025 Vol. 46 No. 12 P. 6092–6102

Добавлено: 1 мая 2026 г.

On the minimum number of maximal distance-k independent sets in trees

Талецкий Д. С., / Series arXiv "math". 2026.

Добавлено: 1 мая 2026 г.

On Arithmetic Mirror Symmetry for smooth Fano fourfolds

Овчаренко М. А., / Series arXiv "math". 2026.

Добавлено: 30 апреля 2026 г.

Natural hazard database from Internet publications: text mining with a large language model

Деркачева А. А., Сакиркина М. А., Краев Г. Н. и др., /. 2026.

Добавлено: 28 апреля 2026 г.

Influence of the Normal Magnetic Component to Magnetotail Current Sheet Forma

Domrin V. I., Malova H. V., V. Yu. Popov и др., Cosmic Research 2026 Vol. 64 No. 2 P. 238–252

Добавлено: 27 апреля 2026 г.

Asymmetric Equilibrium Structures of Superthin Current Sheets: The Asymmetry of Plasma Sources

Tsareva O. O., Malova H. V., V. Yu. Popov и др., Plasma Physics Reports 2026 Vol. 52 No. 2 P. 179–185

Добавлено: 27 апреля 2026 г.

On Suspension Equivalent Homeomorphisms

Починка О. В., Яковлев Е. И., Шмуклер В. И., Russian Journal of Nonlinear Dynamics 2026

Добавлено: 24 апреля 2026 г.

Blobbed topological recursion and KP integrability

Казарян М. Э., Дунин-Барковский П. И., Бычков Б. С. и др., Selecta Mathematica, New Series 2026 Vol. 32 Article 25

Добавлено: 23 апреля 2026 г.

The universal gl-weight system and the chromatic polynomial

Казарян М. Э., Ландо С. К., Коданева Н. М., Journal of Geometry and Physics 2026 No. 225 Article 105841

Добавлено: 23 апреля 2026 г.

Разработка микросервиса ADP для идентификации источников выбросов на основе машинного обучения с подкреплением

Кычкин А. В., Черницин И. А., Прикладная информатика 2026 Т. 21 № 1 С. 40–58

Представлены результаты разработки программного микросервиса, встраиваемого в системы мониторинга качества атмосферного воздуха для поддержки процессов идентификации промышленных источников загрязнений. Выброс и последующее распространение вредных веществ в приземистых слоях атмосферы происходит в динамике и характеризуется высокой неопределенностью из‑за особенностей технологических установок, их режимов работы, влияния рельефа местности, зданий и метеофакторов. Зависимости между местоположением источника выброса и ...

Добавлено: 23 апреля 2026 г.

2026 International Conference on Artificial Intelligence, Computer, Data Sciences and Applications (ACDSA)

IEEE, 2026.

Добавлено: 21 апреля 2026 г.

О некоторых свойствах многочленов, наименее уклоняющихся от нуля на положительной полуоси по экспоненциальной норме

Галкин О. Е., Галкина С. Ю., Ястребова И. Ю., Журнал Средневолжского математического общества 2026 Т. 28 № №1 С. 11–30

Многочлены, наименее уклоняющиеся от нуля, играют важную роль в теории и практике использования численных методов. С их помощью можно решать задачи оптимизации свойств различных вычислительных алгоритмов. Наша работа посвящена изучению многочленов, наименее уклоняющихся от нуля на луче в экспоненциальной норме. В настоящей статье мы обсуждаем вопрос о существовании, единственности и характеризации многочленов, наименее уклоняющихся от нуля ...

Добавлено: 20 апреля 2026 г.

Ising models on the hydrogen peroxide and other lattices

Qin X., Deng Y., Щур Л. Н. и др., / Series arXiv "math". 2026. No. 2603.02962.

Добавлено: 20 апреля 2026 г.

Algorithmic overlaps as thermodynamic variables: from local to cluster Monte Carlo dynamics in critical phenomena

Пиле Я. Э., Deng Y., Щур Л. Н., / Series arXiv "math". 2026. No. 2604.10254.

Добавлено: 20 апреля 2026 г.

On weak solutions to the 1d compressible Navier-Stokes equations: a Lipschitz continuous dependence on data in weaker norms and an error of their homogenization

Zlotnik Alexander, / Series arXiv "math". 2026. No. 2602.03481v1.

Добавлено: 18 апреля 2026 г.

Comparative Analysis of Incentive-Based and Structural Control in Games on Networks with Linear Best Response

Петров И. В., Doklady Mathematics 2026 Vol. Volume 112 P. S103–S110

Добавлено: 17 апреля 2026 г.

Asymptotic expansion of self-consistent energy levels of hydrogen atom in ortogonal electric and magnetic fields

A. V. Pereskokov, Theoretical and Mathematical Physics 2026 Vol. 226 No. 3 P. 470–484

Добавлено: 12 апреля 2026 г.

Моделирование развития компетентности магистрантов на основе вариационного принципа

Колачев Н. И., Адамский А. И., Дроздов Д. С. и др., Моделирование и анализ данных 2026 Т. 16 № 1 С. 157–176

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

Добавлено: 10 апреля 2026 г.

On the dimension of the space of static potentials on three-manifolds

Медведев В. О., / Series arXiv "math". 2026.

We investigate the interplay between the dimension of the space of static potentials and the geometric and topological structure of the underlying static three-manifold. A partial classification of boundaryless static manifolds is obtained in terms of this dimension. We also treat the case of static manifolds with boundary. In particular, we prove that if a ...

Добавлено: 3 апреля 2026 г.

Using predefined vector systems to speed up neural network multimillion class classification

Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.

Добавлено: 2 апреля 2026 г.

О СЛОЖНОСТИ ПРОБЛЕМЫ ТОТАЛЬНОЙ ВЫВОДИМОСТИ В НЕУКОРАЧИВАЮЩИХ И КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИКАХ

Дудаков С. М., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 524 № 1 С. 11–18

В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и ...

Добавлено: 18 марта 2026 г.

Homogeneous maximizers of the Blaschke-Santalo-type functionals

Колесников А. В., / Series arXiv "math". 2025.

Добавлено: 13 февраля 2026 г.

Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection

Сорокин К. С., Бекетов М. Е., Онучин А. и др., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.

Обнаружение сообществ в сложных сетях — фундаментальная проблема, открытая для новых подходов в различных научных областях. Мы представляем новый метод обнаружения сообществ, основанный на потоке Риччи на графах. Наша техника итеративно обновляет веса ребер (их метрические длины) в соответствии с их (комбинаторной) версией кривизны Риччи Фостера, вычисленной на основе эффективного расстояния сопротивления между узлами. Известно, ...

Добавлено: 15 января 2026 г.

О вычислительных аспектах максимальной специфичности в вероятностном объяснении

Сперанский С. О., Вестник Новосибирского государственного университета. Серия: Математика, механика, информатика 2011 Т. 11 № 4 С. 78–93

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

Добавлено: 27 декабря 2025 г.