Сокращение первого порядка

В информатике редукция первого порядка — это очень сильный тип редукции между двумя вычислительными задачами в теории сложности вычислений . Редукция первого порядка — это редукция, при которой каждый компонент ограничен классом FO задач, вычисляемых в логике первого порядка .

Поскольку у нас есть ${\mbox{FO}}\subsetneq {\mbox{L}}$, сокращения первого порядка являются более сильными сокращениями, чем сокращения пространства журнала .

Многие важные классы сложности закрыты при редукции первого порядка, и многие традиционные полные задачи также являются полными первого порядка (Иммерман, 1999, стр. 49-50). Например, ST-связность является FO-полной для NL , а NL закрыта при FO-редукциях (Immerman 1999, стр. 51) (как и P , NP и большинство других «хороших» классов).

Ссылки

• Иммерман, Нил (1999). Описательная сложность . Нью-Йорк: Springer-Verlag. ISBN  0-387-98600-6 .