Спектр предложения - Spectrum of a sentence

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

Определение

Позволять ψ быть приговором в логика первого порядка. В спектр из ψ это набор натуральных чисел п такая, что существует конечная модель для ψ с п элементы.

Если словарь для ψ состоит только из символов отношения, тогда ψ можно рассматривать как приговор в экзистенциальная логика второго порядка (ESOL) количественно оценивается по отношениям, по пустому словарю. А обобщенный спектр набор моделей общего предложения ESOL.

Примеры

• Спектр формулы первого порядка

${\displaystyle \exists z,o~\forall a,b,c~\exists d,e}$

${\displaystyle a+z=a=z+a~\land ~a\cdot z=z=z\cdot a~\land ~a+d=z}$

${\displaystyle \land ~a+b=b+a~\land ~a\cdot (b+c)=a\cdot b+a\cdot c~\land ~(a+b)+c=a+(b+c)}$

${\displaystyle \land ~a\cdot o=a=o\cdot a~\land ~a\cdot e=o~\land ~(a\cdot b)\cdot c=a\cdot (b\cdot c)}$

является ${\displaystyle \{p^{n}\mid p{\text{ prime}},n\in \mathbb {N} \}}$, набор степеней простое число. Действительно, с ${\displaystyle z}$ за ${\displaystyle 0}$ и ${\displaystyle o}$ за ${\displaystyle 1}$, это предложение описывает набор поля; то мощность из конечное поле это степень простого числа.

• Спектр монадической логической формулы второго порядка ${\displaystyle \exists S,T~\forall x~\left\{x\in S\iff x\not \in T\land ~f(f(x))=x\land ~x\in S\iff f(x)\in T\right\}}$ это набор четное числа. В самом деле, ${\displaystyle f}$ это биекция между ${\displaystyle S}$ и ${\displaystyle T}$, и ${\displaystyle S}$ и ${\displaystyle T}$ являются разделом вселенной. Следовательно, мощность вселенной четна.
• Множество конечного и ко-конечного множества - это множество спектров логики первого порядка с отношением преемника.
• Набор в конечном итоге периодических наборов - это набор спектров монадической логики второго порядка с унарной функцией. Это также набор спектров монадической логики второго порядка с функцией преемника.

Характеристики

Теорема Феджина это результат описательная теория сложности который утверждает, что набор всех свойств, выражаемых в экзистенциальных логика второго порядка это именно класс сложности НП. Это примечательно, так как это характеристика класса NP, которая не использует модель вычислений, такую ​​как Машина Тьюринга. Теорема была доказана Рональд Феджин в 1974 году (собственно, в 1973 году в докторской диссертации).

Эквивалентность машинам Тьюринга

Как следствие, Джонс и Селман показали, что множество является спектром тогда и только тогда, когда оно находится в классе сложности NEXP.^[1]

Одно из направлений доказательства - показать, что для каждой формулы первого порядка ${\displaystyle \varphi }$, проблема определения, существует ли модель формулы мощность п эквивалентен проблема выполнения формулы полиномиального размера в п, который находится в NP (n) и, следовательно, в NEXP входных данных задачи (число п в двоичной форме, которая представляет собой строку размера log (п)).

Это делается путем замены каждого экзистенциальный квантор в ${\displaystyle \varphi }$ с дизъюнкция над всеми элементами модели и заменяя каждый универсальный квантор с соединение по всем элементам модели. Теперь каждый предикат относится к элементам в модели, и, наконец, каждое появление предиката для определенных элементов заменяется новой пропозициональной переменной. Равенства заменяются их истинными ценностями в соответствии с их назначениями.

Например:

${\displaystyle \forall {x}\forall {y}\left(P(x)\wedge P(y)\right)\rightarrow (x=y)}$

Для модели мощности 2 (т. Е. п= 2) заменяется на

${\displaystyle {\big (}\left(P(a_{1})\wedge P(a_{1})\right)\rightarrow (a_{1}=a_{1}){\big )}\wedge {\big (}\left(P(a_{1})\wedge P(a_{2})\right)\rightarrow (a_{1}=a_{2}){\big )}\wedge {\big (}\left(P(a_{2})\wedge P(a_{1})\right)\rightarrow (a_{2}=a_{1}){\big )}\wedge {\big (}\left(P(a_{2})\wedge P(a_{2})\right)\rightarrow (a_{2}=a_{2}){\big )}}$

Что затем заменяется на${\displaystyle {\big (}\left(p_{1}\wedge p_{1}\right)\rightarrow \top {\big )}\wedge {\big (}\left(p_{1}\wedge p_{2}\right)\rightarrow \bot {\big )}\wedge {\big (}\left(p_{2}\wedge p_{1}\right)\rightarrow \bot {\big )}\wedge {\big (}\left(p_{2}\wedge p_{2}\right)\rightarrow \top {\big )}}$

куда ${\displaystyle \top }$ это правда, ${\displaystyle \bot }$ это ложь, и ${\displaystyle p_{1}}$, ${\displaystyle p_{2}}$ суть пропозициональные переменные. в данном конкретном случае последняя формула эквивалентна ${\displaystyle \neg (p_{1}\wedge p_{2})}$, что выполнимо.

Другое направление доказательства - показать, что для каждого набора двоичных строк, принимаемых недетерминированной машиной Тьюринга, работающей в экспоненциальном времени (${\displaystyle 2^{cx}}$ для входной длины x) существует формула первого порядка ${\displaystyle \varphi }$ такой, что набор чисел, представленных этими двоичными строками, является спектром ${\displaystyle \varphi }$.

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

Другие свойства

Множество спектров теории замкнуто относительно союз, пересечение, сложение и умножение. Вообще говоря, неизвестно, замыкается ли набор спектров теории дополнением; это так называемая проблема Ассера.

Смотрите также

• Спектр теории

Рекомендации

• Феджин, Рональд (1974). "Обобщенные спектры первого порядка и распознаваемые множества за полиномиальное время" (PDF). В Карп, Ричард М. (ред.). Сложность вычислений. Proc. Syp. Приложение. Математика. SIAM-AMS Proceedings. 7. С. 27–41. Zbl  0303.68035.
• Грэдель, Эрих; Колайтис, Phokion G .; Либкин Леонид; Маартен, Маркс; Спенсер, Джоэл; Варди, Моше Ю.; Венема, Иде; Вайнштейн, Скотт (2007). Теория конечных моделей и ее приложения. Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag. Дои:10.1007/3-540-68804-8. ISBN  978-3-540-00428-8. Zbl  1133.03001.
• Иммерман, Нил (1999). Описательная сложность. Тексты для выпускников по информатике. Нью-Йорк: Springer-Verlag. стр.113 –119. ISBN  0-387-98600-6. Zbl  0918.68031.
• Дюран, Арно; Джонс, Нил; Марковский, Иоганн; Подробнее, Малика (2012). «Пятьдесят лет спектральной проблемы: обзор и новые результаты». Бюллетень символической логики. 18 (4): 505–553. arXiv:0907.5495. Bibcode:2009arXiv0907.5495D. Дои:10.2178 / bsl.1804020.

Специфический

1. * Джонс, Нил Д .; Селман, Алан Л. (1974). «Машины Тьюринга и спектры формул первого порядка». J. Symb. Бревно. 39 (1): 139–150. Дои:10.2307/2272354. JSTOR  2272354. Zbl  0288.02021.