리소스 경계 측정

루츠의 자원 경계 조치는 르베그 측도를 복잡도 등급에 일반화한 것이다.그것은 원래 잭 러츠에 의해 개발되었다.르베그 측정이 유클리드 공간 $\mathbb {R} ^{n}$ $\mathbb {R} ^{n}$ ${\$ 의 부분 집합 크기를 정량화하는 방법을 제공하듯이 $\mathbb {R} ^{n}$ 자원 경계 측도는 복잡도 등급의 부분 집합 크기를 분류하는 방법을 제공한다.

예를 들어, 컴퓨터 과학자들은 일반적으로 복잡도 등급 P(다항식 시간에 해결할 수 있는 모든 의사결정 문제의 집합)가 복합성 등급 NP(다항식 시간에는 확인할 수 있지만 반드시 해결할 수는 없는 모든 의사결정 문제의 집합)와 같지 않다고 믿는다.P는 NP의 하위 집합이기 때문에, 이것은 NP가 P보다 더 많은 문제를 포함하고 있다는 것을 의미할 것이다."P가 NP가 아니다"보다 더 강한 가설은 "NP가 p-measure 0을 가지고 있지 않다"는 것이다.여기서 p-측정(p-measurement)은 P가 포함된 복잡도 등급 E의 하위 집합에 대한 르베그 측정을 일반화한 것이다.P는 p-measurement 0을 가지고 있다고 알려져 있으므로, "NP가 p-measure 0을 가지고 있지 않다"는 가설은 NP와 P가 동일하지 않을 뿐만 아니라, 측정-이론적 의미에서 NP가 "P보다 훨씬 크다"는 것을 의미할 것이다.

정의

$\{0,1\}^{\infty }$ $\{0,1\}^{\infty }$ $\{0,1\}^{\infty }$ ∞} ${\$ 은 $\{0,1\}^{\infty }$ (는) 모든 무한 이진 시퀀스의 집합이다.2진법 확장을 고려해 단위 간격의 실제 숫자를 무한 이진 시퀀스로 볼 수 있다.또한 언어에 n번째 이진 문자열(사전순으로)이 포함되어 있는 경우에만 시퀀스의 n번째 비트를 1로 설정하여 언어(이진 문자열 집합)를 무한 이진 시퀀스로 볼 수 있다.따라서 단위 간격과 복잡도 등급(언어 집합)의 실수 집합은 둘 다 무한 이항 시퀀스의 집합으로 볼 수 있으며, 따라서 실수 집합의 크기를 측정하는 데 사용되는 측정 이론의 기법을 복잡도 등급 측정에 적용할 수 있다.그러나 계산 가능한 각 복잡도 클래스는 계수 가능한 요소 수만 포함하므로(계산 가능한 언어의 수는 계수 가능하기 때문에), 각 복잡도 클래스는 0을 측정한다.그러므로 복잡성 계층 내부의 이론을 측정하기 위해서, 우리는 무한정 시퀀스의 계수 가능한 집합에서 의미 있게 작동하는 대안적인 측정을 정의해야 한다.이 조치가 의미가 있으려면 각 복잡성 등급의 기본 정의, 즉 주어진 자원 범위 내에서 해결할 수 있는 계산적 문제에 의해 정의된다는 것을 반영해야 한다.

자원 경계 조치의 토대는 빌레의 마팅헤일즈 제형이다.마팅게일은 $d:\{0,1\}^{*}\to [0,\infty )$ : $d:\{0,1\}^{*}\to [0,\infty )$ { 0 $d:\{0,1\}^{*}\to [0,\infty )$ $d:\{0,1\}^{*}\to [0,\infty )$ $d:\{0,1\}^{*}\to [0,\infty )$ → $d:\{0,1\}^{*}\to [0,\infty )$ [ 0 $d:\{0,1\}^{*}\to [0,\infty )$ $d:\{0,1\}^{*}\to [0,\infty )$ ) $d:\{0,1\}^{*}\to [0,\fty )$ 함수로서, 모든 $d:\{0,1\}^{*}\to [0,\infty )$ 유한 문자열 w에 대해,

{\

}{2}}}

.

(이것은 빌의 원래 마팅게일 정의인데, 후에 조셉 레오 두브가 확장했다.)A martingale d is said to succeed on a sequence $S\in \{0,1\}^{\infty }$ if $\limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,$ where $S\upharpoonright n$ is the first n bits of S. A martingale succeeds on a set of seX의 모든 순서에 성공하면 X $X\subseteq \{0,1\}^{\infty }$ $X\subseteq \{0,1\}^{\infty }$ $X\subseteq \{0,1\}^{\infty }$ ∞ {\ $displaystyle$ X $\subseteq \{0,1\}^{\inful }}}}}}}}.$

직관적으로 마팅게일은 약간의 한정된 금액(예: 1달러)으로 시작하는 도박꾼이다.그것은 일련의 비트들을 무한정 읽는다.유한 접두사 $w\in \{0,1\}^{*}$ $w\in \{0,1\}^{*}$ $w\in \{0,1\}^{*}$ ∗} $w\in \{0,1\}^{*}$ {\ $displaystyle$ w\ $in$ \{ $0,1\}^{*}}}}}}}}$ 을 읽고 나면 다음 비트는 0이 되고, 나머지 돈은 1이 된다는 현재의 돈의 일부를 베팅한다 $w\in \{0,1\}^{*}$ 다음에 등장하는 비트 위에 어떤 돈이 놓이던 간에 두 배로 늘게 되고, 등장하지 않은 비트 위에 놓인 돈을 잃게 된다.모든 돈을 걸어야 하지만, 그 돈의 절반을 각 조각에 올려놓음으로써 "아무것도 베팅하지 않을" 수도 있다.마팅게일 d의 경우 d(w)는 w 줄을 읽고 d가 가진 돈의 양을 나타낸다.마팅게일의 정의는 마팅게일이 어떤 베팅을 할지를 계산하는 것이 아니라 게임의 제약적인 성격 때문에 어떤 베팅을 할 것인지 계산하는 것이 아니라, d(w), d(w0), d(w1)의 값을 알고 있으면 끈 w를 보고 d가 0과 1에 놓은 베팅을 계산하는 데 충분하다.마팅게일이 지금까지 본 스트링의 입력대로 취하는 함수라는 사실은 배치된 베팅이 이미 읽은 비트의 함수일 뿐이라는 것을 의미한다. 다른 어떤 정보도 베팅에 영향을 미치지 않을 수 있다(다른 정보는 마팅게일의 일반화 이론에서 소위 여과라고 함).

$X\subseteq \{0,1\}^{\infty }$ 관련된 주요 결과는 세트 X $X\subseteq \{0,1\}^{\infty }$ x{ $X\subseteq \{0,1\}^{\infty }$ , $X\subseteq \{0,1\}^{\infty }$ $X\subseteq \{0,1\}^{\infty }$ ∞ { { { $\$ X $\subseteq \{0,1\}^{\inflt }}}}}}}$ 이(가) X에서 성공하는 마팅게일이 있는 경우에만 Lebegue가 0이라는 $X\subseteq \{0,1\}^{\infty }$ Vil의 관측이다.따라서 우리는 측정값 0 집합을 집합의 모든 요소에서 성공하는 마팅게일이 존재하는 것으로 정의할 수 있다.

이러한 유형의 측정을 복잡도 등급으로 확장하기 위해, Lutz는 마팅게일의 계산 능력을 제한할 것을 고려했다.예를 들어, 어떤 마팅게일을 허용하는 대신, 우리는 마팅게일을 다항식 시간 계산이 가능하도록 요구한다면, 우리는 p-measurement의 정의를 얻는다: 만약 세트에서 성공하는 다항식 시간 계산 가능한 마팅게일이 있다면 시퀀스 집합에 p-measure 0이 있다.우리는 그것의 보완물이 p-measure 0을 갖는 경우 p-measure 1을 갖도록 집합을 정의한다.예를 들어, NP에 p-measure 0이 없다는 위에서 언급한 추측을 증명하면, 모든 NP에서 어떤 다항 시간 마팅게일이 성공하지 못한다는 것을 증명하는 것과 같다.

거의 완료됨

C에 문제가 있고 C의 다른 문제가 C에 있는 경우 복잡도 등급 C에 대해 문제가 거의 완전하다.좀 더 구체적으로, 문제를 줄이는 C의 문제의 부분집합은 자원 경계 측정의 관점에서 하나의 척도다.이것은 수업에서 완료되는 문제보다 더 약한 요구 사항이다.

참조

van Melkebeek, Dieter (2001), Randomness and Completeness in Computational Complexity, Springer, ISBN 3-540-41492-4, archived from the original on 2011-07-19

외부 링크

자원 경계 측정 참고 문헌 목록

Search

리소스 경계 측정

네임스페이스

더

목차

정의

거의 완료됨

참조

외부 링크