계산가능함수

계산 가능한 함수는 계산가능성 이론에서 연구의 기본 대상이다. 연산 가능한 함수는 함수의 작업을 수행할 수 있는 알고리즘이 존재한다면, 즉 함수 영역의 입력이 해당 출력을 반환할 수 있다면 함수가 계산 가능하다는 점에서 알고리즘의 직관적인 개념의 공식화된 아날로그다. 계산 가능한 함수는 튜링 기계나 레지스터 기계와 같은 계산의 어떤 구체적인 모델을 언급하지 않고 연산성을 논하기 위해 사용된다. 그러나 모든 정의는 특정한 연산 모델을 참조해야 하지만 모든 유효한 정의는 동일한 종류의 함수를 산출한다. 계산 가능한 기능 집합을 발생시키는 연산성의 특정 모델은 튜링-컴퓨팅 기능과 일반적인 재귀 기능이다.

계산 가능한 함수의 정확한 정의 이전에 수학자들은 종종 계산 가능한 비공식 용어를 사용했다. 이 용어는 그 이후 계산 가능한 함수와 동일시되었다. 이러한 함수의 유효 연산성은 효율적으로 계산될 수 있음을 의미하지 않는다는 점에 유의하십시오(즉, 합리적인 시간 내에 계산됨). 실제로 일부 효과적으로 계산할 수 있는 기능의 경우 알고리즘의 실행 시간이 입력 길이와 함께 기하급수적으로(또는 심지어 초단순적으로) 증가한다는 점에서 알고리즘을 계산하는 알고리즘이 매우 비효율적이라는 것을 보여줄 수 있다. 효율적인 계산이 가능한 연산성과 계산 복잡성 연구 기능의 분야.

Church-Turing 논문에 따르면 계산 가능한 함수는 기계식 계산 장치를 사용하여 계산 가능한 함수로 제한 없이 시간과 저장 공간이 주어진다. 동등하게, 이 논문은 함수가 알고리즘을 가지고 있는 경우에만 계산될 수 있다고 기술한다. 이러한 의미에서의 알고리즘은 시간이 무한하고 펜과 종이를 무제한으로 공급하는 사람이 따를 수 있는 일련의 과정으로 이해된다는 점에 유의한다.

블럼 공리는 계산 가능한 함수들의 집합에 대한 추상적인 계산 복잡성 이론을 정의하는 데 사용될 수 있다. 계산 복잡성 이론에서 계산 가능한 함수의 복잡성을 결정하는 문제를 함수 문제로 알려져 있다.

정의

함수의 계산가능성은 비공식적인 개념이다. 그것을 설명하는 한 가지 방법은 어떤 함수의 값이 효과적인 절차에 의해 얻어질 수 있다면 그 함수를 계산할 수 있다고 말하는 것이다. 만일이, 어떤k-tuple x}자연수의{\displaystyle \mathbf{)}를 주어진 효과적인 절차이다 더 엄격함, 함수 f:Nk→ N{\displaystyle f:\mathbb{N}^{k}\rightarrow \mathbb{N}}, f협정에서()){\displaystyle f(\mathbf{x})}.[1]값을 생산할 것으로 계산할 수 있는 있다.w이 정의에 따르면, 이 글의 나머지 부분은 계산 가능한 함수가 정확히 많은 자연수를 인수로 간주하고 단일 자연수인 값을 산출한다고 가정한다.

이 비공식적 설명의 반대자로서, 여러 가지 공식적이고 수학적 정의가 존재한다. 연산 가능한 함수의 등급은 다음을 포함한 많은 동등한 연산 모델에서 정의될 수 있다.

이러한 모델들은 기능, 입력, 출력물에 대해 서로 다른 표현을 사용하지만, 번역은 어떤 두 모델 사이에 존재하며, 따라서 모든 모델은 본질적으로 동일한 종류의 기능을 기술하고 있어 형식적인 계산가능성은 자연스럽고 너무 좁지 않다는 의견을 갖게 한다.^[2]

예를 들어 계산 가능한 함수를 μ-recursive 함수로 공식화할 수 있는데, 이는 유한한 자연수 튜플을 취하고 하나의 자연수(위와 같이)를 반환하는 부분함수다. 상수, 계승, 투영 함수를 포함하는 부분함수의 가장 작은 부류로 구성, 원시 재귀, μ 연산자에 의해 폐쇄된다.

동등하게 계산 가능한 함수는 튜링 기계나 레지스터 기계와 같은 이상화된 컴퓨팅 에이전트에 의해 계산될 수 있는 함수로 공식화될 수 있다. 공식적으로 말하면 부분 함수 $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ : $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ → $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ ${\$ f $:\mathb {N} ^{k}\$ 오른쪽 $화살표 \mathb {N}}은($ 는) 다음 속성을 가진 컴퓨터 프로그램이 존재하는 경우에만 계산할 수 있다 $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ .

$f(\mathbf {x} )$ ( $f(\mathbf {x} )$ ) $f(\mathbf {x})$ 을 $f({\mathbf x})$ (를) 정의한 경우, 컴퓨터 $f(\mathbf {x} )$ 에 $f({\mathbf x})$ 저장된 $\mathbf {x}$ f $f(\mathbf {x} )$ $f(\mathbf {x} )$ ) ${\displaystyle$ $\mathbf$ { $x}$ 입력 x ${\displaystyle$ \ $mathbf {x}$ 에서 프로그램이 종료된다.
$f(\mathbf {x} )$ ( $f(\mathbf {x} )$ ) ${\displaystyle$ f $(\mathbf {x} )}$ 이 $f({\mathbf x})$ (가) 정의되지 않으면 프로그램이 입력 $\mathbf {x}$ ${\$ 에서 종료되지 않는다.

계산 가능한 함수의 특성

계산 가능한 함수의 기본 특성은 함수의 계산 방법을 알려주는 유한 절차(알고리즘)가 있어야 한다는 것이다. 위에 열거한 연산 모델은 절차가 무엇이고 어떻게 사용되는지에 대해 서로 다른 해석을 주지만, 이러한 해석은 많은 특성을 공유한다. 컴파일러가 하나의 컴퓨터 언어로 된 명령어를 읽을 수 있고 다른 언어로 된 명령어를 방출할 수 있는 것처럼, 이러한 모델들이 계산 가능한 기능의 동등한 클래스를 제공한다는 사실은 각 모델이 다른 모델에 대한 절차를 읽고 모방할 수 있다는 사실에서 기인한다.

Enderton [1977]은 계산 가능한 함수를 계산하기 위한 절차의 다음과 같은 특성을 제공한다. Turing [1936], Rogers [1967] 등이 유사한 특성을 부여했다.

"절차에 대해서는 길이가 한정된 정확한 지시(즉, 프로그램)가 있어야 한다." 따라서 계산 가능한 모든 함수는 함수를 계산하는 방법을 완전히 설명하는 유한 프로그램을 가져야 한다. 지시사항만 따르면 기능을 계산할 수 있다. 추측이나 특별한 통찰이 필요하지 않다.
"절차서에 f의 영역에서 k-tuple x가 주어지면, 한정된 수의 이산 스텝 후에 절차를 종료하고 f(x)를 생성해야 한다." 직관적으로, 절차는 계산의 각 단계에서 무엇을 해야 하는지를 다루는 구체적인 규칙과 함께 단계별로 진행된다. 기능의 값이 반환되기 전에 정밀하게 많은 단계만 수행할 수 있다.
"만약 그 절차가 f의 영역에 있지 않은 k-tuple x가 주어진다면, 그 절차는 영원히 멈추지 않고 계속될지도 모른다. 또는 어느 시점(즉, 지시사항 중 하나는 실행할 수 없음)에 고착될 수 있지만, x에서 f 값을 산출하는 시늉을 해서는 안 된다." 따라서 f(x)에 대한 값이 발견되면 정확한 값이어야 한다. 결과를 생성하는 경우에만 절차가 정확하다고 정의되기 때문에 컴퓨팅 에이전트는 정확한 결과와 잘못된 결과를 구별할 필요가 없다.

계속해서 Enderton은 계산 가능한 함수에 대한 절차의 세 가지 요구사항에 대한 몇 가지 설명을 나열한다.

그 절차는 이론적으로 임의의 큰 논쟁에 효과가 있어야 한다. 예를 들어, 그 주장이 지구의 원자 수보다 작다고 가정하지 않는다.
이 절차는 출력을 생성하기 위해 정밀하게 여러 단계를 거친 후에 중단해야 하지만 중단하기 전에 임의적으로 여러 단계를 수행할 수 있다. 시간 제한은 가정하지 않는다.
성공적인 연산 중에 이 절차는 한정된 양의 저장 공간만 사용할 수 있지만 사용되는 공간의 양에는 제한이 없다. 절차가 요구할 때마다 추가 보관 공간을 제공할 수 있다고 가정한다.

요약하자면, 다음과 같은 경우 이 뷰에 기초하여 함수를 계산할 수 있다.

제한되지 않은 스토리지 공간에 의존할 가능성이 있는 도메인에서 입력된 경우, 한정된 수의 정확한 모호하지 않은 지침에 의해 구성된 절차(프로그램, 알고리즘)를 따름으로써 해당 출력을 제공할 수 있다.
한정된 수의 스텝에서 그러한 출력(할트)을 반환한다.
만약 그것의 영역에 없는 입력이 주어진다면, 그것은 결코 멈추지 않거나 고착되지 않는다.

계산 복잡성 연구 분야는 성공적인 계산에서 허용되는 시간 및/또는 공간에 대해 규정된 한계로 기능한다.

계산 가능한 집합 및 관계

자연수 집합을 계산 가능한 총 함수 $f$ 가 있으면 계산 가능한 집합(동기어: 재귀, 해독 가능)이라고 하며, 계산 가능한 총 함수 f가 $있으면$ $f () n$ = 1이고, $에 없으면 n$ f() = 0이다.

각 숫자에 $대해$ 계산 $가능$ 한 함수 f가 있는 경우 자연수 집합을 계산적으로 열거할 수 있는 집합(동기어: 재귀적으로 열거할 수 있는, 반간격)이라고 한다. f $() n$ 는 집합에 있는 경우에만 정의된다. 따라서 집합은 계산 가능한 함수의 도메인인 경우에만 계산적으로 열거된다. 열거형이라는 단어는 자연수의 비어 있지 않은 부분 집합에 대해 다음과 같기 때문에 사용된다.

$B$ 계산 가능한 함수의 영역이다.
$B$ 계산 가능한 총 함수의 범위. 무한대일 경우 함수는 주입으로 가정할 수 있다.

집합이 함수 $f$ 의 범위인 경우, 리스트 $f (0),$ $f (1), ...$ 가 의 모든 요소를 포함하기 때문에 함수를 의 열거로 볼 수 있다.

자연수에 대한 각 미세한 관계는 해당 유한한 자연수열의 집합으로 식별할 수 있기 때문에 계산 가능한 관계와 계산적으로 열거할 수 있는 관계의 개념은 집합에 대한 그들의 유사성에서 정의될 수 있다.

격식어

컴퓨터 과학의 계산가능성 이론에서는 형식 언어를 고려하는 것이 일반적이다. 알파벳은 임의의 집합이다. 알파벳에 있는 단어는 알파벳에서 기호의 유한한 배열이다. 같은 기호는 두 번 이상 사용될 수 있다. 예를 들어, 이진 문자열은 정확히 알파벳 ${0, 1}$ 에 있는 단어들이다. 언어는 고정된 알파벳에 있는 모든 단어 모음의 하위 집합이다. 예를 들어, 정확히 3개의 이진 문자열을 포함하는 모든 이진 문자열의 집합은 이진 알파벳을 통한 언어다.

공식 언어의 주요 특성은 주어진 단어가 언어에 있는지 여부를 결정하는 데 필요한 난이도다. 일부 코딩 시스템은 계산 가능한 함수가 언어의 임의 단어를 입력으로 받아들일 수 있도록 개발되어야 한다. 이것은 보통 일상적인 것으로 간주된다. 알파벳을 통한 각 단어에 대해 $f () w$ = $1$ 이 언어에 속하면 f() = 1이 되고, 단어가 언어에 속하지 않으면 $f () w$ = $0$ 이 되는 계산 가능한 $함수$ 가 있으면 언어를 계산 가능한(동기어: 재귀, 해독 가능)이라고 한다. 따라서 언어는 임의의 단어가 언어에 있는지 여부를 정확하게 알 수 있는 절차가 있는 경우에만 계산이 가능하다.

$f$ ()가 $w$ 언어에 있는 경우에만 정의되는 계산 가능한 함수 $f$ 가 있는 경우 언어는 계산적으로 열거된다(동음어: 재귀적으로 열거할 수 있고 반간격). 열거할 수 있는 용어는 계산적으로 열거할 수 있는 자연수 집합에서와 동일한 어원을 가지고 있다.

예

다음 기능을 계산할 수 있다.

유한 영역을 가진 각 함수, 예를 들어, 자연수의 유한 시퀀스.
각 상수함수 f : N^k → N, f(n₁, ...n_k) :=n
덧셈 f : N² → N, f(n₁,n₂) :=n₁₂ + n
두 숫자 중 가장 큰 공통점
A Bézout 계수(A Bézout
숫자의 가장 작은 주요 요인

f와 g를 계산할 수 있는 경우 f + g, f g g, $\color {Blue}f\circ g$ g ${\$ f가 단항인 $\color {Blue}f\circ g$ 경우 max(f,g), $arg max {y f (x)$ 및 그 이상의 조합이 있다.

다음 예는 어떤 알고리즘이 함수를 계산하는지 알 수 없지만 함수를 계산할 수 있다는 것을 보여준다.

f( $n$ ) = 1, f(n) = 0의 소수확장에 최소한 n개의 연속형 fiv의 시퀀스가 있을 경우, 그렇지 않을 경우 f(n) = 0을 계산할 수 있는 함수. (함수 f는 계산 가능한 상수 1 함수 중 하나이거나, n < k>일 경우 f(n) = 1이고 n n k일 경우 f(n) = 0인 k가 있다. 그러한 모든 기능은 계산 가능하다. π의 소수확장에 임의로 긴 fiv의 런이 있는지 알 수 없기 때문에 그 함수 중 f가 어느 함수인지 알 수 없다. 그럼에도 불구하고 f함수는 계산이 가능해야 한다는 것을 우리는 알고 있다.)
(Busy Beaver 함수 σ과 같은) 자연수열의 각 유한 세그먼트를 계산할 수 있다. 예를 들어, 각 자연수 n에 대해 전체 σ-시퀀스를 계산하는 알고리즘이 없는 것과 대조적으로 —(0), σ(1), σ(2), ... σ(n)을 계산하는 알고리즘이 존재한다. Thus, "Print 0, 1, 4, 6, 13" is a trivial algorithm to compute Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); similarly, for any given value of n, such a trivial algorithm exists (even though it may never be known or produced by anyone) to compute Σ(0), Σ(1), Σ(2), ..., Σ(n).

교회-튜링 논문

Church-Turing 논문은 위에 열거된 세 가지 특성을 가진 절차에서 계산 가능한 모든 함수는 계산 가능한 함수라고 말한다. 이 세 가지 성질은 공식적으로 명시되지 않기 때문에, Church-Turing 논문은 증명될 수 없다. 논문에서 흔히 다음과 같은 사실을 증거로 삼는다.

많은 등가 연산 모델이 알려져 있으며, 모두 계산 가능한 함수(또는 어떤 경우에는 약한 버전)에 대한 동일한 정의를 제공한다.
일반적으로 계산 가능한 것으로 간주되는 더 강력한 연산 모델은 제안되지 않았다.

Church-Turing 논문은 계산 절차에 대한 구체적인 설명을 함으로써 특정 기능이 계산 가능하다는 것을 정당화하기 위해 때때로 증명에 사용된다. 이는 논문의 모든 그러한 용도가 일부 연산 모델에서 함수에 대한 공식적인 절차를 작성하는 지루한 과정에 의해 제거될 수 있다고 믿기 때문에 허용된다.

Provability

함수(또는 유사하게, 집합)를 부여하면 연산 가능한 경우뿐만 아니라, 이것이 특정 증명 시스템(보통 우선 순서는 페아노 산술)에서 증명될 수 있는지 여부에도 관심이 있을 수 있다. 연산 가능한 것으로 증명될 수 있는 함수를 가능한 총함수라고 한다.

입증 가능한 총함수의 집합은 반복적으로 열거된다. 즉, 연산성을 증명하는 모든 해당 증거를 열거함으로써 모든 입증 가능한 총함수를 열거할 수 있다. 이것은 증명 시스템의 모든 증거를 열거하고 관련 없는 증거를 무시함으로써 이루어질 수 있다.

재귀적으로 정의된 함수에 대한 관계

재귀적 정의에 의해 정의된 함수에서, 각 값은 동일한 함수 또는 다른 함수의 이전에 정의된 다른 값의 고정된 1차 공식에 의해 정의되며, 이는 단순히 상수일 수도 있다. 이것들 중 일부는 원시적인 재귀 기능이다. 그러한 모든 기능은 다음과 같은 총계일 수 있다. 이러한 k-ary 함수 f의 경우 각 값 $f(n_{1},n_{2}...n_{k})$ $f(n_{1},n_{2}...n_{k})$ , $f(n_{1},n_{2}...n_{k})$ 2 $f(n_{1},n_{2}...n_{k})$ . $f(n_{1},n_{2}...n_{k})$ . . $f(n_{1},n_{2}...n_{k})$ $f(n_{1},n_{2}...n_{k})$ ) ${\displaystyle f(n_{1},n_{2}...$ $n_{k}}}$ 은(는) 정의를 거꾸로 따라 반복적으로 계산할 수 있으며 $f(n_{1},n_{2}...n_{k})$ , 한정된 반복 횟수의 반복 후에(쉽게 증명될 수 있듯이) 상수에 도달한다.

모든 전체 기능이 원시적인 재귀적인 것은 아니기 때문에 그 반대는 사실이 아니다. 실제로 모든 원시 재귀 함수를 열거하고 모든 n, m: en(n,m) = f_n(m)에 대해 함수를 정의할 수 있다. 여기서 f는_n n번째 원시 재귀 함수(k-arry 함수의 경우 f(m_n,m...m)로 설정된다. 자, g(n) = en(n,n)+1은 대각화 인수에 의해 확실히 총체적이지만 원시적 재귀는 아니다: 만약 g = f와_j 같은 j가 있었다면 g(j) = en(j,j)+1 = f_j(j)+1 = f(j)+1 = g(j)+1, 모순을 얻었을 것이다. (모든 원시 재귀 함수의 괴델 번호는 원시 재귀 함수의 값은 열거할 수 없지만 원시 재귀 함수에 의해 열거될 수 있다.)

그러한 기능 중 하나는 총체적이지만 원시적 재귀성은 아닌 Ackermann 기능이다: 재귀적으로 정의되기 때문에 그 연산성을 입증하는 것은 정말로 쉽다(그러나, 유사한 대각화 인수도 재귀적 정의에 의해 정의된 모든 기능에 대해 구축될 수 있다, 따라서, 증명 가능한 총함수들은 방어할 수 없다.반복적으로^{[citation needed]}.

타당하지 않은 총 함수 수

견실한 증명 시스템에서는, 모든 입증 가능한 총함수는 사실 총함수지만, 그 반대는 사실이 아니다: 충분히 강하고 건전(페아노 산수를 포함)한 모든 1차 증명 시스템에서는, 증명 시스템에서는 총함수로서 증명할 수 없는 총함수의 존재를 (다른 증명 시스템에서는) 증명할 수 있다.

계산 가능한 총 함수가 그것들을 생산하는 튜링 기계를 통해 열거되는 경우, 증명 시스템이 건전하다면, 앞에서 주어진 가능한 총 함수의 열거법을 사용하여 위에서 사용한 것과 유사한 대각화 인수에 의해 위의 문장이 표시될 수 있다. 관련 증명서를 열거하는 튜링 머신을 사용하며, 모든 입력 n에 대해 n번째 증거에 따라 계산하는 튜링 머신을 호출하여 f(n_n) (여기서 f는_n 이 열거에 의한 n번째 함수)를 호출한다. 그러한 튜링 기계는 교정 시스템이 건전하면 정지할 것을 보장한다.

입력 불가능한 기능 및 해결할 수 없는 문제

모든 계산 가능한 함수는 그것을 계산하는 방법에 대한 명확하고 모호하지 않은 지시를 제공하는 유한한 절차를 가지고 있다. 더욱이, 이 절차는 계산 모델에 의해 사용되는 유한한 알파벳으로 인코딩되어야 하므로 계산 가능한 함수는 셀 수 없이 많을 뿐이다. 예를 들어 함수는 비트 문자열(문자 $alphabet$ = ${0,$ 1)을 사용하여 인코딩할 수 있다.

실수는 셀 수 없기 때문에 대부분의 실수는 계산할 수 없다. 계산 가능한 숫자를 참조하십시오. 자연수에 대한 일련의 미세한 함수는 계산할 수 없기 때문에 대부분은 계산할 수 없다. 그러한 기능의 구체적인 예로는 바삐 비버, 콜모고로프 복잡성, 또는 차이틴의 상수처럼 계산 불가능한 숫자의 숫자를 출력하는 모든 기능이 있다.

마찬가지로, 자연수의 대부분의 하위 집합은 계산할 수 없다. 그 중단 문제는 건설된 첫 번째 세트였다. 데이비드 힐버트가 제안한 Entscheidungsprobroblem은 어떤 수학적 문장(자연수로 부호화됨)이 사실인지를 판단하는 효과적인 절차가 있는지 물었다. 튜링과 교회는 1930년대에 독립적으로 이 자연수들의 집합은 계산할 수 없다는 것을 보여주었다. Church-Turing 논문에 따르면, 이러한 계산을 수행할 수 있는 효과적인 절차(알고리즘 포함)는 없다.

계산성 확장

상대적 계산성

함수의 계산가능성의 개념은 임의의 자연수 A 집합과 상대화될 수 있다. 함수 f는 A에 대한 액세스를 허용하는 수정으로 계산 가능한 함수의 정의를 만족하는 경우(A에 비해 동등하게 A-computable 또는 계산 가능) A에서 연산 가능한 것으로 정의된다. 계산 가능한 함수 상대 계산성의 개념과 마찬가지로, 많은 다른 계산 모델에서 동등한 정의를 제공할 수 있다. 이것은 일반적으로 주어진 정수가 A의 멤버인지를 묻는 추가적인 원시 연산을 통해 연산 모델을 보완함으로써 이루어진다. 우리는 또한 f가 g로 그 그래프로 g를 식별함으로써 g로 계산될 수 있다는 것에 대해 말할 수 있다.

고등재귀론

초산술 이론은 빈 집합의 튜링 점프의 계산 가능한 순서형 번호로 계산될 수 있는 집합들을 연구한다. 이것은 제2차 산술 언어의 보편적 공식과 실존적 공식에 의해 정의된 집합과 하이퍼컴퓨팅의 일부 모델에 해당한다. 어떤 집합이든 E-재귀 함수에 대한 논거로 사용할 수 있는 E-재귀 이론과 같이 훨씬 더 일반적인 재귀 이론이 연구되었다.

하이퍼 컴퓨팅

Church-Turing 논문은 계산 가능한 함수가 알고리즘을 포함한 모든 함수를 포함한다고 기술하고 있지만, 알고리즘이 반드시 보유해야 하는 요건을 완화하는 광범위한 함수의 등급에 대해 고려할 수 있다. 하이퍼컴퓨팅 분야는 정상적인 튜링 연산을 뛰어넘는 연산 모델을 연구한다.

참고 항목

참조

^ Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second ed.). USA: Elsevier. p. 209. ISBN 0-12-238452-0.
^ Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second ed.). USA: Elsevier. p. 208,262. ISBN 0-12-238452-0.

커틀랜드, 나이젤. 계산 가능성. 1980년 캠브리지 대학 출판부
Enderton, H.B. 재귀 이론의 요소들. 수리논리편람(North-Holland 1977) 페이지 527-566.
로저스, H. 재귀 함수 및 유효 계산 이론(McGrow-Hill 1967)
Turing, A. (1937), On Computable Numbers, Entscheidungsprobroblem에 응용 프로그램 포함. 런던 수학 학회의 절차, 시리즈 2, 42권(1937), 페이지 230–265. 1965년 M. Davis (edd.)에서 다시 출판된 The Underdicabled, Raven Press, Hewlett, NY.

[1] Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second ed.). USA: Elsevier. p. 209. ISBN 0-12-238452-0.

[2] Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second ed.). USA: Elsevier. p. 208,262. ISBN 0-12-238452-0.

[2]

v t 중요 복잡성 클래스(추가)
실현 가능한 것으로 간주됨	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-완전 ZPP RP BPP BQP APX
실행 불가능한 것으로 의심됨	UP NP NP-완전 NP-하드 공동 NP 공동 NP-완전 AM QMA PH ⊕P PP #P #P-완전 IP 프스페이스 PSpace-완전
실현 불가능한 것으로 간주됨	엑스트라타임 NEXPTIME 엑스포스페이스 2-EXPTIME 초등 PR R RE 모두
클래스 계층	다항식 계층 구조 지수 계층 구조 그르제고르차이크 계층 구조 산술 계층 구조 부울 계층 구조
계급가족	디타임 NTIME 디스페이스 NSpace 확률적으로 확인할 수 있는 증거 인터랙티브 프루프 시스템

Search