ELEMENTARY

계산 복잡도 이론에서 복잡도 종류 ${\displaystyle {\mathsf {ELEMENTARY}}}$는 초등 재귀 함수에 의해 제한된 시간 내에 풀 수 있는 결정 문제들로 구성된다. 이와 동등하게, 이는 제한된 횟수의 반복을 갖는 반복 지수 함수에 의해 제한된 시간 내에 풀 수 있는 문제들이다.

모든 초등 재귀 함수는 이러한 형태의 시간 제한 내에서 계산될 수 있으므로, 초등 재귀 함수만을 사용하여 계산되는 모든 결정 문제는 복잡도 종류 ${\displaystyle {\mathsf {ELEMENTARY}}}$에 속한다.

시간 계층 정리는 ${\displaystyle {\mathsf {ELEMENTARY}}}$에 완전 문제가 존재하지 않음을 시사한다. ${\displaystyle {\mathsf {ELEMENTARY}}}$ 외부의 문제들은 비초등 문제이다.

정의

가장 빠르게 증가하는 초등 재귀 함수는 ${\displaystyle 2^{n}}$과 같은 지수 함수를 유한한 횟수 ${\displaystyle k}$만큼 반복하여 얻어지며, 형태는 다음과 같다. $${\displaystyle \left.{\begin{matrix}2^{\scriptstyle 2^{\scriptstyle 2^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle n}}}}}}\end{matrix}}\right\}k{\text{번 반복}}.}$$

따라서 ${\displaystyle {\mathsf {ELEMENTARY}}}$는 다음 종류들의 합집합이다.

$${\displaystyle {\begin{aligned}{\mathsf {ELEMENTARY}}&=\bigcup _{k\in \mathbb {N} }k{\mathsf {{\mbox{-}}EXP}}\\&={\mathsf {DTIME}}\left(2^{n}\right)\cup {\mathsf {DTIME}}\left(2^{2^{n}}\right)\cup {\mathsf {DTIME}}\left(2^{2^{2^{n}}}\right)\cup \cdots .\end{aligned}}}$$ 이것은 때때로 반복 지수 시간(iterated exponential time)이라고 묘사하지만, 이 용어는 더 일반적으로 테트레이션 함수에 의해 제한된 시간을 의미한다.

특성

내용주

각주

• Engelfriet, Joost (1991), “Iterated stack automata and complexity classes”, 《Information and Computation》 95 (1): 21–75, doi:10.1016/0890-5401(91)90015-T, MR 1133778 
• Friedman, Harvey (1999), 〈Some decision problems of enormous complexity〉 (PDF), 《14th Annual IEEE Symposium on Logic in Computer Science, Trento, Italy, July 2-5, 1999》, {IEEE} Computer Society, 2–12쪽, doi:10.1109/LICS.1999.782577, ISBN 0-7695-0158-3, MR 1942515 
• Hella, Lauri; Turull-Torres, José María (2006), “Computing queries with higher-order logics”, 《Theoretical Computer Science》 355 (2): 197–214, doi:10.1016/j.tcs.2006.01.009, ISSN 0304-3975