City: Санкт-Петербург Новосибирск Казань Language: Русский English

Разрешимость и сложность в модальной логике
Введение в модальную логику


What: Lecture
When: Sunday, 20 October 2019, 15:30–17:00
Where: ПОМИ РАН

Description

  • Финитная аппроксимируемость и конечная аксиоматизируемость
  • Теорема Харропа
  • Пример: доказательство разрешимости логики ${\bf S}4$ через доказательство ее фининтной аппроксимируемости
  • $\operatorname{co-NP}$-полнота логики ${\bf S}5$ и $\operatorname{PSPACE}$-полнота логики ${\bf S}4$