1차감소

컴퓨터 과학에서, 1차적인 감소는 계산 복잡성 이론에서 두 가지 계산 문제 사이의 매우 강력한 유형의 감소다.1차 감축은 각 구성부품이 1차 논리적으로 계산할 수 있는 문제의 FO 등급에 속하도록 제한되는 감축이다.

${\displaystyle FO}$ ${\displaystyle ⊊}$ L ${\$$FO}}\subsetneq{\mbox{L$ 1차 주문 감소는 로그 공간 감소보다 더 강력하다.

많은 중요한 복잡성 클래스는 1차 주문 감소로 마감되며, 전통적인 전체 문제들 중 다수도 1차 주문 완료다(Umerman 1999 페이지 49-50).예를 들어, ST 연결성은 NL의 경우 FO-완전이며, NL은 FO 감소(Emmerman 1999, 페이지 51)에 따라 폐쇄된다(P, NP 및 기타 대부분의 "정상적인" 등급).

참조

• Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. ISBN 0-387-98600-6.

이 수학적 논리 관련 논문은 단조롭다.위키피디아를 확장하여 도울 수 있다.

• v
• t