Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
17 октября 2016 г. 18:30–20:30, г. Москва, МИАН (ул. Губкина, 8), ауд. 313 + Zoom
 


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

Святловский М.

Московский физико-технический институт, факультет инноваций и высоких технологий

Количество просмотров:
Эта страница:108

Аннотация: Строго позитивные логики описывают множества импликаций A->B, где A и B - модальные формулы, строящиеся лишь с помощью конъюнкции и модальностей типа "ромб" из переменных и константы "истина". Будет указан полиномиальный разрешающий алгоритм для строго позитивного фрагмента логики конечных иррефлексивных линейных порядков GL.3. До недавнего времени этот фрагмент рассматривался как возможная строго позитивная логика с co-NP полной проблемой выводимости, однако автору удалось опровергнуть эту гипотезу (по модулю P не = NP).
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024