Спектр предложения
- Спектр предложения в математической логике — набор натуральных чисел, представляющий размер конечной модели, в которой данное предложение истинно.
- Набор натуральных чисел является спектром тогда и только тогда, когда он распознается за недетерминированное экспоненциальное время.
- Определение спектра включает предложение в логике первого порядка и конечную модель из n элементов.
- Обобщенный спектр представляет собой набор моделей общего предложения экзистенциальной логики второго порядка.
- Теорема Фейгина утверждает, что набор всех свойств, выражаемых в экзистенциальной логике второго порядка, соответствует классу сложности NP.
- Множество спектров логики первого порядка связано с классом сложности NEXP.
- Набор спектров теории замкнут при объединении, пересечении, сложении и умножении.
- Проблема Ассера касается замкнутости набора спектров теории путем дополнения.
Полный текст статьи: