WikiDer > Редукция первого порядка

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

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

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

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

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

Этот математическая логика-связанная статья является заглушка. Вы можете помочь Википедии расширяя это. v т е