|
|
Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
17 октября 2016 г. 18:30–20:30, г. Москва, МИАН (ул. Губкина, 8), ауд. 313 + Zoom
|
|
|
|
|
|
Полиномиальный алгоритм распознавания выводимости в строго позитивной логике линейных порядков
Святловский М. Московский физико-технический институт, факультет инноваций и высоких технологий
|
Количество просмотров: |
Эта страница: | 108 |
|
Аннотация:
Строго позитивные логики описывают множества импликаций A->B, где A и B - модальные формулы, строящиеся
лишь с помощью конъюнкции и модальностей типа "ромб" из переменных и константы "истина".
Будет указан полиномиальный разрешающий алгоритм для строго позитивного фрагмента логики конечных
иррефлексивных линейных порядков GL.3. До недавнего времени этот фрагмент рассматривался как возможная строго позитивная логика с co-NP полной проблемой выводимости, однако автору удалось опровергнуть эту гипотезу (по модулю P не = NP).
|
|