블럼 공리

계산 복잡성 이론에서 블럼 공리 또는 블럼 복잡성 공리는 계산 가능한 함수 집합에 대한 복잡성 측정의 바람직한 특성을 지정하는 공리이다.이 공리는 1967년에 Manuel Blum에 의해 처음 정의되었다.^[1]

중요한 것은 블럼의 스피드업 정리 및 갭 정리는 이러한 공리를 만족시키는 어떤 복잡성 측도 지탱하고 있다는 점이다.이러한 공리를 만족시키는 가장 잘 알려진 척도는 시간(즉, 실행 시간)과 공간(즉, 메모리 사용)이다.

정의들

블럼 복잡도 측정은${\displaystyle }$$\phi {\displaystyle }$,${\displaystyle \mathrm{\phi }}$) ${\displaystyle (\varphi ,\Phi )}$과(와) 쌍이며, φ ${\displaystyle \varphi }$은(와) 부분 계산 가능한 함수 $P{\displaystyle {\mathbf{}}^{}}$(${\displaystyle 1^{}}$ $){\$^(1)의 번호 지정이다.

${\displaystyle \Phi :\mathb {N} \to \mathbf {P}^{(1)}$

다음과 같은 블럼 공리를 만족시킨다.Gödel 번호 지정 ${{\displaystyle \$$varphi$$$$_{i},$$$부분 계산 가능 함수 $\phi {\displaystyle \mathrm{}}$( i$){\$$displaystyle \$$varphi$ $_{i$$}$에 ${\displaystyle \mathrm{i번째}}$ 부분 계산 가능 함수를 $\phi {\displaystyle {}_{}}$ ${\displaystyle i_{}}$${\$$displaystysty \Phi$_{i}라고 쓴다$.$

• $\phi {\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$와 $\phi {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle i_{}}$ ${\$의 도메인은 동일하다$$.
• $\mathb{{N}$ $phi_{i$\mathb $\{3} \Phi_{i}(x)=t\}$ 집합은 반복적이다.

예

• ${\displaystyle }$(${\displaystyle }$$\phi {\displaystyle \mathrm{}}$ ,${\displaystyle \mathrm{\phi }}$) ${\displaystyle (\varphi ,\Phi )}$은(는) by ${\displaystyle \Phi }$이(가) i에 의해 코딩된 계산에 필요한 시간 또는 메모리(또는 그 일부 적절한 조합)인$$ 경우 복잡성 측정값이다$$.
• ${\displaystyle }$(${\displaystyle \phi }$ ,${\displaystyle \phi }$) ${\displaystyle (\varphi ,\varphi )}$은(는) 두 번째 공리에 실패하므로 복잡성 측정이 아니다.

복잡도 클래스

총 계산 가능한 함수 $f{\displaystyle }$ ${\displaystyle f}$의 계산 가능한 함수의 복잡성$$ 클래스는 다음과 같이 정의할 수 있다.

$[\displaystyle C(f):=\\{\varphi _{i}\in \mathbf {P} ^{(1) \all x.\\\\Phi _{i}(x)\leq f(x)\}}}}$

${\displaystyle C^{0}(f):=\{h\in C(f) \mathrm {codom}(h)\subseteq \{0,1\}\}}}}$

${\displaystyle C(f}$) ${\displaystyle C(f)}$은(는) $f{\displaystyle }${\$displaystyle f$}보다 복잡도가 작은 모든 계산 가능한 함수의 집합이다$.$ $f)$는 $f$ ${\displaystyle f}$보다 복잡도가 작은 모든 부울 값 함수의 집합이다$.$ 이러한 함수를 집합에 대한 지표 함수로 간주하면 $C{\displaystyle {}^{}}$.${\displaystyle 0^{}}$( ${\displaystyle f}$) ${\displaystyle C^{0}(f)}$은(는) 집합의 복잡성 등급으로 생각할 수 있다$$.

참조