서술적 복잡성 이론

서술적 복잡성은 계산적 복잡성 이론과 그것들의 언어를 표현하는 데 필요한 논리 유형에 따라 복잡성 클래스를 특징짓는 유한한 모델 이론의 한 분야다.예를 들어, 다항식 계층 구조에서 모든 복잡성 클래스의 결합인 PH는 정확히 2차 논리학의 문장으로 표현 가능한 언어의 등급이다.이러한 복잡성과 유한 구조의 논리 사이의 연결은 결과를 한 영역에서 다른 영역으로 쉽게 이전할 수 있게 하여 새로운 입증 방법을 촉진하고 주요 복잡성 등급이 그것들을 정의하는데 사용되는 특정한 추상적 기계에 얽매이지 않고 어떻게든 "자연적"이라는 추가적인 증거를 제공한다.

구체적으로, 각각의 논리 시스템은 그 안에서 표현 가능한 일련의 질의를 생산한다.한정된 구조로 제한될 때 쿼리는 전통적인 복잡성 이론의 계산적 문제와 일치한다.

서술적 복잡성의 첫 번째 주요 결과는 1974년 로널드 파긴이 보여준 파긴의 정리였다.그것은 NP가 실존적 2차 순서 논리, 즉 관계, 기능, 하위 집합에 대한 보편적 정량화를 제외한 2차 순서 논리로서 정확하게 표현할 수 있는 언어 집합임을 확립했다.많은 다른 계층들이 나중에 그런 방식으로 특징지어졌다.

설정

우리가 논리 형식주의를 사용하여 계산 문제를 설명할 때, 입력은 유한한 구조로, 그 구조의 요소는 담론의 영역이다.일반적으로 입력은 문자열(비트 또는 알파벳 위에 있는)이며, 논리 구조의 요소는 문자열의 위치를 나타내거나, 입력은 그래프이고 논리 구조의 요소는 그 정점을 나타낸다.입력 길이는 각 구조물의 크기로 측정된다.구조가 어떻든 간에 "E${\displaystyle }$( ${\displaystyle x}$ ,${\displaystyle }$y${\displaystyle }$) ${\displaystyle E(x,y)}$는 x에서 y까지 에지가 있으면 참이다"(구조가$$ 그래프로 되어 있는 경우) 또는 "${\displaystyle }$($){\displaystyle P(n)$는 문자열의 n번째 글자가 1이면 참이다$$"와 같이 시험할 수 있는 관계가 있다고 가정할 수 있다.이들 관계는 1차 논리체계의 술어들이다.우리는 또한 상수를 가지고 있는데, 상수는 각각의 구조의 특별한 요소인데, 예를 들어, 우리가 그래프에서 도달가능성을 확인하려면, 우리는 두 개의 상수 s(시작)와 t(단말)를 선택해야 할 것이다.

서술적 복잡성 이론에서 우리는 종종 요소들 위에 총체적인 순서가 있고 요소들 간의 평등을 확인할 수 있다고 가정한다.이를 통해 요소들을 숫자로 고려할 수 있다$:{\displaystyle }$ 요소 x는 (${\displaystyle \mathrm{n}}$-${\displaystyle }$1 )$${\$displaystyle (n-1)$ 요소 y가 숫자 n을 나타낸다. y x ${\displaystyle$ y$<x$Thanks to this we also may have the primitive predicate "bit", where ${\displaystyle bit(x,k)}$ is true if only the kth bit of the binary expansion of n is 1. (We can replace addition and multiplication by ternary relations such that ${\displaystyle plus(x,y,z)}$ is true iff ${\displ$$aystyle x+y=z}$ 및 $t$ ${\displaystyle i}$ ${\displaystyle m}$ e ${\displaystyle s(x,}$ ${\displaystyle y,}$ z${\displaystyle }$) ${\displaystyle times(x,y,z)}$은(는) if $x{\displaystyle }$ x ${\displaystyle \ast }$ ${\displaystyle y}$= z ${\displaystyle x*y=z}$인 경우 참이다$$.$$

복잡성 클래스의 특성 개요

만약 우리가 우리 자신을 후계자 관계와 기본적인 산술 술어가 있는 순서 구조로 제한한다면, 우리는 다음과 같은 특징을 얻게 된다.

• 1차 로직은 경계 깊이의 다항식 크기 회로에 의해 인식되는 언어인 클래스 AC를⁰ 정의하는데, 이는 일정한 시간에 동시 랜덤 액세스 기계에 의해 인식되는 언어와 같다.^[1]
• 대칭 또는 결정론적 전이성 폐쇄 연산자로 증강되는 1차 논리에서는 로그 공간에서 해결할 수 있는 L이 발생한다.^[2]
• Transitive Closure 연산자와 함께 1차 로직은 비결정론적 로그 공간에서 해결할 수 있는 문제인 NL을 산출한다.^[3]
• 최소 고정점 운영자가 있는 1차 논리에서는 결정론적 다항 시간에서 해결할 수 있는 문제인 P를 제공한다.^[3]
• 실존적 이차 논리학은 NP를 산출한다.^[3]
• 보편적 2차 논리(실존적 2차 수량화 제외)는 co-NP를 산출한다.^[4]
• 2차 로직은 다항식 계층 구조 PH에 해당한다.^[3]
• 타동성 폐쇄(전속성 여부를 불문함)가 있는 2차 논리에서는 다항식 공간에서 해결할 수 있는 문제인 PSPACE를 산출한다.^[5]
• 최소 고정점 운영자가 있는 2차 로직은 지수 시간 내에 해결할 수 있는 문제인 EXPTIME을 제공한다.^[6]
• HO는 ENTERIC과^[7] 동일함

하위 폴리놈 시간

연산자가 없는 FO

회로 복잡성에서 임의 술어가 있는 1차 로직은 AC 계층 구조에서 첫 번째 클래스인 AC와⁰ 동일하다고 보여질 수 있다.실제로, 회로의 노드로 FO의 기호에서 자연적으로 번역된 것이 있는데, ${\displaystyle ,}$ ,${\displaystyle \mathrm{}}$∃ , ∃ ${\displaystyle$$$\$forall$,\$exists$}은$$$$$$ 크기가 n인 $\wedge {\displaystyle }$ ${\displaysty$ \$land },$ $\vee {\displaystyle }$ ${\displaysty \lor }$이다.산술적 술어로 된 서명의 1차 논리에서는 교류 로그 시간에 구성 가능한 회로에 대한 AC⁰ 회로 계열의 제한을 특징으로 한다.^[8]순서 관계만 있는 서명의 1차 로직은 항성 없는 언어의 집합에 해당한다.^[9][10]

전이성 폐쇄 논리

1차 로직은 2진 관계의 전이적 폐쇄성을 계산하는 연산자로 증강될 때 표현력이 크게 향상된다.그 결과로 나타나는 전이성 폐쇄 논리는 순서가 지정된 구조물에 대한 비결정성 로그 공간(NL)의 특성을 나타내는 것으로 알려져 있다.이것은 Imerman에 의해 NL이 보완(즉, NL = co-NL)으로 닫혀 있음을 보여주기 위해 사용되었다.^[11]

타동성 폐쇄 연산자를 결정론적 타동성 폐쇄로 제한할 때, 결과 로직은 명령된 구조물의 로그 공간을 정확하게 특징짓는다.

2차 크롬 공식

후속 기능이 있는 구조물에 대해서도 2차 크롬 공식으로 NL을 특성화할 수 있다.

SO-Krom은 첫 번째 순서 정량자가 범용이고 공식의 정량자가 없는 부분이 크롬 형태로서, 첫 번째 순서 공식이 분리의 결합체라는 것을 의미하며, 각 "분산"에는 최대 두 개의 변수가 있다.모든 2차 크롬 공식은 실존적인 2차 크롬 공식과 동등하다.

SO-Krom은 후속 기능이 있는 구조물에서 NL을 특징으로 한다.^[12]

다항식 시간

순서가 지정된 구조에서 1차 최소 고정점 로직은 PTIME을 캡처한다.

첫 번째 순서 최소 고정점 논리

FO[LFP]는 최소 고정점 운영자에 의한 1차 로직을 확장한 것으로, 단조표식의 고정점을 표현한다.이것은 재귀 표현 능력으로 1차 논리를 강화한다.이머만과 바디가 독자적으로 보여준 이머만-바르디 정리는 FO[LFP]가 명령된 구조물에 PTIME을 특징짓는 것을 보여준다.^[13][14]

2022년을 기점으로, 비변조 구조물에 PTIME을 특징짓는 자연논리가 존재하는지 여부는 여전히 열려 있다.

아비테보울-비아누 정리에는 FO[LFP]=라고 되어 있다.FO[LFP]=인 경우에만 모든 구조물에 대한 FO[PFP]FO[PFP], 따라서 P=PSpace인 경우에만 해당된다.이 결과는 다른 고정점으로 확대되었다.^[15]

2차 뿔풍뎅이

후속 기능이 있는 경우, PTIME은 2차 Horn Formulae로 특징 지을 수 있다.

SO-Horn은 첫 번째 순서의 정량자가 모두 보편적이며 공식의 정량자가 없는 부분이 Horn 형식이며, 이는 OR의 큰 AND라는 것을 의미하며, 각 "OR"에서 가능한 한 변수를 제외한 모든 변수가 부정되는 등, 분리 정규 형식의 SO 공식으로 정의할 수 있는 부울 질의의 집합이다.

이 세분류는 후속 기능이 있는 구조물에서 P와 동일하다.^[16]

그러한 공식들은 실존적인 2차 혼 논리에서는 혼전 공식으로 변형될 수 있다.^[12]

비결정론적 다항식 시간

파긴의 정리

실존적 2차적 논리로 공리화할 수 있는 구조물의 그러한 종류에 의해 복잡도 등급 NP가 정확히 특징지어졌다는 로널드 파긴의 1974년 증거는 서술적 복잡성 이론의 출발점이었다.^[4][17]

실존 공식의 보완은 보편적인 공식이기 때문에, co-NP가 보편적인 2차 순서의 논리에 의해 특징지어지는 것이 바로 뒤따른다.^[4]

따라서 제한되지 않은 2차 순서 논리는 다항식 계층 구조 PH와 동일하다.더 정확히 말하면, 우리는 파긴의 정리를 다음과 같이 일반화했다.두 번째 순서의 실존적 및 보편적 정량자가 k를 대체하는 혼전 정상 형태의 공식 집합은 다항식 계층의 k번째 수준을 특징짓는다.^[18]

대부분의 다른 복잡도 등급의 특성화와 달리, 파긴의 정리 및 일반화는 구조물에 대한 전체 순서를 전제로 하지 않는다.실존적 2차 순서의 논리 자체가 2차 변수를 이용한 구조에서 가능한 총질서를 지칭할 만큼 충분히 표현되어 있기 때문이다.^[19]

비욘드 NP

부분 고정점은 PSPACE임

다항 공간인 PSPACE에서 계산할 수 있는 모든 문제의 등급은 보다 표현력 있는 부분 고정점 연산자로 1차 로직을 증가시킴으로써 특징지을 수 있다.

부분 고정점 논리 FO[PFP]는 부분 고정점 연산자와 함께 1차 로직을 확장한 것으로, 공식의 고정점이 있으면 표현하고, 그렇지 않으면 '거짓'을 반환한다.

부분 고정점 논리는 순서가 지정된 구조물에 대한 PSPACE의 특성을 나타낸다.^[20]

Transitive closure is PSPACE

2차 로직은 1차 로직과 같은 방식으로 타전 폐쇄 사업자가 확장할 수 있어 SO[TC]가 된다.TC 사업자는 이제 2차 변수를 인수로 받아들일 수도 있다.SO[TC]는 PSpace를 특징으로 한다.순서는 2차 논리에서도 참조할 수 있으므로, 이 특성화는 순서 구조를 전제로 하지 않는다.^[21]

기본 함수

기본 함수의 시간 복잡도 클래스 ELAST는 고차 논리 공식으로 인식할 수 있는 구조물의 복잡도 클래스인 HO로 특징지을 수 있다.고차 논리란 고차 계량자를 가진 1차 논리 및 2차 논리의 확장이다.$i{\displaystyle }$ ${\displaystyle i}$ 순서$$ 및 비결정론 알고리즘 사이에는 관계가 있으며, 이 알고리즘의 시간은 $i{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle i-1}$ 수준의$$ 지수들로 제한된다.^[22]

정의

우리는 고차 변수를 정의한다.순서 > ${\displaystyle$i>1}의 $변수는$$아리티{\displaystyle }$ k ${\displaystyle$ k$}$을(를) 가지며$$ 순서 $i{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle i-1}$의 $모든{\displaystyle }$ k ${\displaystyle k}$ -tuple을 나타낸다$.$그것들은 보통 대문자로 쓰여지고 순서를 나타내기 위해 자연수를 지수로 한다.고차 논리란 고차 변수에 대해 정량화를 추가하는 1차 공식의 집합이므로 다시 정의하지 않고 FO 기사에 정의된 용어를 사용할 것이다.

HO${\displaystyle ^{i}}$ is the set of formulae with variables of order at most ${\displaystyle i}$. HO${\displaystyle _{j}^{i}}$ is the subset of formulae of the form ${\displaystyle \phi =\exists {\overline {X_{1}^{i}}}\forall {\overline$${X_{2}^{i}}}\dots Q{\overline {X_{j}^{i}}}\psi }$, where ${\displaystyle Q}$ is a quantifier and ${\displaystyle Q{\overline {X^{i}}}}$ means that ${\displaystyle {\overline {X^{i}}}}$ is a tuple of variable of order ${\displaystyle i}$ with the same quantification.$따라서{\displaystyle }$ HO ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$은(는$)$$$$순서$ i {\$displaystyle$ i$}$의 정량자를$$교대로$$ $사용$한 공식이며$$,$$$\exists {\displaystyle \mathrm{}}$ ${\displaysty \exists$ $\}$부터 $시작$하여 ${\displaystyle \mathrm{순서}}$ i ${\displaystyle -}$1 {\$displaystystyle i-1$까지입니다.

Using the standard notation of the tetration, ${\displaystyle \exp _{2}^{0}(x)=x}$ and ${\displaystyle \exp _{2}^{i+1}(x)=2^{\exp _{2}^{i}(x)}}$. ${\displaystyle \exp _{2}^{i+1}(x)=2^{$$2{\displaystyle }$$^{2^{2^{\filename ^{2^{x}}}}}:$ i ${\displaystyle i}$ 곱하기$$ $2{\displaystyle \mathrm{}}$ ${\displaystyle 2}$ 포함$$.

정상형식

모든 순서 $i{\displaystyle }$ ${\displaystyle i}$ th의$$ 공식은 혼전 정규식의 공식과 동등하며, 여기서 우리는 $먼저{\displaystyle }$ i ${\displaystyle$ i$}$의 변수에 대한 계량화를 작성하고, 그 다음 순서 $i{\displaystyle }$ -$[displaysty i-1$}의 공식은 정상 형식이다$$.

복잡도 등급과의 관계

HO는 초등기능의 초등등급과 같다.To be more precise, ${\displaystyle {\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))}$, meaning a tower of ${\displaystyle (i-2)}$ 2s, ending with ${\displaystyle n^{c}}$, where ${\displaystyle c}$ is a constant. A special case of this is that ${\displaystyle \exists {\mathsf {SO}}={\mathsf {HO}}_{0}^{2}={\mathsf {NTIME}}(n^{O(1)})={\color {Blue}{\mathsf {NP}}}}$, which is exactly Fagin's theorem.Using oracle machines in the polynomial hierarchy, ${\displaystyle {\mathsf {HO}}_{j}^{i}={\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)})^{\Sigma _{j}^{\mathsf {P}}})}$

메모들

참조

• Neil, Immerman (1999). Descriptive complexity. Springer. ISBN 0-387-98600-6. OCLC 901297152.

외부 링크

• 다이어그램을 포함한 Neil Imerman의 서술적 복잡성 페이지