의사결정 트리 모델

계산 복잡도에서 의사결정 나무 모델은 알고리즘이 기본적으로 의사결정 나무, 즉 적응적으로 수행된 일련의 쿼리 또는 테스트로 간주되는 계산 모델이다. 따라서 이전 테스트의 결과가 다음에 수행될 수 있다.

일반적으로 이러한 테스트는 소수의 결과(예: 예-아니오 질문)를 가지며 신속하게 수행될 수 있습니다(예를 들어 단위 계산 비용으로). 따라서 의사결정 트리 모델에서 알고리즘의 최악의 경우 복잡도는 해당 의사결정 트리의 깊이에 해당합니다.의사결정 트리 모델에서 문제의 계산 복잡도 또는 알고리즘의 이러한 개념을 의사결정 트리 복잡도 또는 쿼리 복잡도라고 합니다.

의사결정 트리 모델은 계산 문제 및 알고리즘의 특정 클래스에 대한 복잡성 이론의 하한을 설정하는 데 중요하다.계산 모델 및 쿼리 알고리즘의 유형에 따라 여러 가지 유형의 의사결정 트리 모델이 도입되었습니다.

예를 들어, Decision Tree 인수는 비교 $n$ 의n개의 \ $displaystyle$ n 항목이 $n$ $n\log(n)$ 의 로그 $n\log(n)$ ( $n\log(n)$ $)\displaystyle$ n $\log(n)$ 비교를 받아야 $n\log(n)$ 함을 나타내기 위해 사용됩니다.비교 종류로 두개의 항목 a, b{\displaystyle a,\,b}의 두 결과(어떤 항목 같다고 가정하)거나.<>b{\displaystyle a<, b}또는 a>b{\displaystyle a>, b}하고 쿼리는 비교 상대입니다. 그러한 정렬 알고리즘만 월을 수행하 비교 종류 결정을 나무로 이 모델에서는, 표현될 수 있다.ese 종류 of 쿼리

비교 트리 및 정렬 하한

Decision Tree는 정렬 알고리즘 및 기타 유사한 문제를 이해하기 위해 자주 사용됩니다. 이는 Ford와 ^[1]Johnson에 의해 처음 수행되었습니다.

예를 들어 지역 비교를 통해, 많은 정렬 알고리즘은 비교 종류, 그것은 그들은 단지 한 입력 시퀀스에 대한 정보를 얻기 때문)1, x2,…,)n{\displaystyle x_{1},x_{2},\ldots ,x_{n}}:시험인지 나는 < x^j{\displaystyle x_{나는}<, x_{j}},)나는)j{\displaystyle x_ 정도씩 생겨나고 있다.{나는}=x_{ $j$ $x_{i}>x_{j}$ x $x_{i}>x_{j}$ > $x_{i}>x_{j}$ j { $displaystyle x_{i$ }> $x_{$ j $x_{i}>x_{j}$ 정렬되는 항목이 모두 구별되고 동일한 경우, 이는 yes 또는 no 질문으로 바꿀 수 있습니다. $x_{i}>x_{j}$ i $x_{i}>x_{j}$ > $x_{i}>x_{j}$ j $x_{i}>x_{j}$ \ $displaystyle x_{i}$ > $x_{j}$ } $。$

이러한 알고리즘은 이진 Decision Tree로 모델링할 수 있습니다.이 경우 쿼리는 비교입니다.내부 노드는 쿼리에 대응하고 노드의 자녀는 질문에 대한 대답이 예 또는 아니오일 때 다음 쿼리에 대응합니다.리프 노드의 경우 출력은 입력 시퀀스가 완전히 정렬된 항목 목록에서 스크램블된 방법을 설명하는 치환 $(\displaystyle\pi)$ 에 $\pi$ 해당합니다.(이 치환의 $\pi ^{-1}$ " - $\pi ^{-1}$ $(\displaystyle$ \pi ^{- $1$ 은 입력 시퀀스의 순서를 변경합니다).

단순한 인수를 통해 비교 정렬에서 $\Omega (n\log(n))$ log $\Omega (n\log(n))$ ( $\Omega (n\log(n))$ ) $\Omega (n\log(n))$ { $displaystyle \Omega ( n$ \ $log$ ( $n$ ) } )비교를 $\Omega (n\log(n))$ 사용할 필요가 있음을 알 수 있습니다.알고리즘이 정확하려면 n{ $displaystyle$ n $}$ 요소의 $n$ $n$ 한 모든 치환을 출력할 수 있어야 합니다.그렇지 않으면 특정 치환에 대한 알고리즘이 실패합니다.따라서 대응하는 Decision Tree에는 적어도 순열 수만큼의 리프가 있어야 합니다 $. n$ ! \ $displaystyle$ n $!$ leave $n!$ }개입니다.n개 $n!$ 의 $!{displaystyle$ n $!}$ 개의 $n!$ 리프가 있는 바이너리 트리의 깊이는 $\log _{2}(n!)=\Omega (n\log _{2}(n))$ 2 $\log _{2}(n!)=\Omega (n\log _{2}(n))$ µ ( $\log _{2}(n!)=\Omega (n\log _{2}(n))$ ! ) $\log _{2}(n!)=\Omega (n\log _{2}(n))$ ( n $){displaystyle \log$ _ ${2}(n!)$ $\log _{2}(n!)=\Omega (n\log _{2}(n))$ 입니다. $=\Omega(n\log _{2}($ n $\log _{2}(n!)=\Omega (n\log _{2}(n))$ 따라서 이는 비교 정렬 알고리즘의 실행 시간 하한입니다.이 경우, 머지소트나 힙소트 등, 이 시간 복잡도를 가지는 수많은 비교 정렬 알고리즘의 존재는,^[2]^{: 91} 경계가 엄격한 것을 나타내고 있습니다.

이 인수는 쿼리 유형에 대해 아무것도 사용하지 않으므로 실제로는 이진 의사결정 트리로 모델링할 수 있는 정렬 알고리즘의 하한을 증명합니다.기본적으로 이것은 올바른 정렬 알고리즘이 입력 시퀀스에 관한 정보의 $적어도2 비트$ 를 $\log_2(n!)$ 학습할 필요가 있다는 정보이론의 인수를 바꿔 쓴 것입니다 $.$ 그 결과, 이것은 랜덤화된 의사결정 트리에도 유효합니다.

다른 결정 트리 하한에서는 쿼리가 비교임을 사용합니다.예를 들어 비교만 사용하여 n개의 $\displaystyle$ n개 $n$ 번호 중 $가장$ 작은 번호를 찾는 작업을 고려합니다.가장 작은 숫자를 결정하기 전에 가장 작은 숫자를 제외한 모든 숫자는 적어도 하나의 비교에서 "손실"되어야 합니다.따라서 최소값을 구하려면 $(style n-1)$ 의 $n-1$ 비교가 필요합니다.(여기서 information-theretic 인수에는 log $\log(n)$ n $)(\displaystyle \log(n))$ 만 표시됩니다).순서 ^[2]^{: 214}통계정보를 계산하는 일반적인 하한에도 동일한 인수가 적용됩니다.

선형 및 대수적 결정 트리

선형 결정 트리는 위의 비교 결정 트리를 실제 $x\in \mathbb {R} ^{n}$ x $x\in \mathbb {R} ^{n}$ $x\in \mathbb {R} ^{n}$ n $x\in \mathbb {R} ^{n}$ \ $display$ x \ $in$ \ $mathbb$ { $R }^$ { $n$ } 를 $x\in \mathbb {R} ^{n}$ 입력으로 하는 계산 함수에 일반화한다.선형 결정 트리의 테스트는 선형 함수입니다.특정 $a_{0},\dots ,a_{n}$ 의 선택 $a_{0},\dots ,a_{n}$ 0 $a_{0},\dots ,a_{n}$ $a_{0},\dots ,a_{n}$ $(\$ a_{0}, $a_{n$ 에 대해 0 $a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}$ + $a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}$ $=$ $a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}$ n i $a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}$ \ $displaystyle a_{0}+\textstyle \sum _ i_n}a_{x}$ _ ${g$ 의 부호를 출력합니다.f 출력). $x_{i}$ 트리는 선형 결정 트리입니다. x i $(\$ })와 $x_{i}$ $x_{j}$ j(\ $displaystyle x_{j})$ 의 비교는 선형 $x_{i}-x_{j}$ x $x_{i}-x_{j}$ - x $(\$ 에 해당하기 $x_{j}$ 때문입니다. 선형 결정 트리는 정의에서 f $(\displaystyle$ f $)$ 만 $f$ 지정할 수 있습니다.섬유는 반공간의 결합과 교차점을 이용하여 구성할 수 있습니다.

대수적 결정 트리는 테스트 함수를 $d도의 다항식$ 으로 할 수 있는 선형 결정 트리의 일반화입니다. 기하학적으로 공간은 반 대수 집합(하이퍼플레인 일반화 $d$ 으로 분할됩니다.

Rabin과 Reingold에 ^[4]의해^[3] 정의된 이러한 의사결정 트리 모델은 종종 계산 ^[5]기하학의 하한을 증명하기 위해 사용됩니다.예를 들어, Ben-Or는 요소 고유성(f $f:\mathbb {R} ^{n}\to \{0,1\}$ $f:\mathbb {R} ^{n}\to \{0,1\}$ $f:\mathbb {R} ^{n}\to \{0,1\}$ $x_{i}=x_{j}$ { $f:\mathbb {R} ^{n}\to \{0,1\}$ , $f:\mathbb {R} ^{n}\to \{0,1\}$ $}$ {\ $displaystyle$ f $:\mathbb {R} ^{n}\to \{0,1$ 이 있음을 보여주었습니다 $f(x)$ $f(x)$ 서 f $f(x)$ ( $f(x)$ x ) { $displaystyle f($ x $f(x)$ )}는 $,$ j, { $displaystyle i}$ 가 $x_{i}=x_{j}$ 하는 $i,j$ 경우에만 0입니다.에는 깊이 $\Omega (n\log(n))$ log $\Omega (n\log(n))$ ( $\Omega (n\log(n))$ $){displaystyle \Omega (n\log(n$ )})}의 대수적 Decision Tree가 필요합니다 $\Omega (n\log(n))$ ^[6]이것은 Dobkin과 Lipton에 ^[7]의해 선형 의사결정 모델에 대해 처음 나타났다.또한 배낭 문제의 선형 결정 트리에 대한 $(\$ n $^{2})$ $n^{2}$ 을 $n^{2}$ 나타내며, 스틸과 ^[8]야오가 대수적 결정 트리로 일반화했다.

부울 의사결정 트리의 복잡성

Boolean Decision Tree의 $f:\{0,1\}^{n}\to \{0,1\}$ $x\in \{0,1\}^{n}$ 은 입력 x $x\in \{0,1\}^{n}$ { $x\in \{0,1\}^{n}$ , 1 $f:\{0,1\}^{n}\to \{0,1\}$ } $x\in \{0,1\}^{n}$ { 0 $f:\{0,1\}^{n}\to \{0,1\}$ , $f:\{0,1\}^{n}\to \{0,1\}$ } $n$ { $f:\{0,1\}^{n}\to \{0,1\}$ , $f:\{0,1\}^{n}\to \{0,1\}$ $}$ {{ $displaystyle$ f $:\$ { $0$ , $1$ \ $}\ to$ \ { $0$ , $1$ \ $x\in \{0,1\}^{n}$ n $f:\{0,1\}^{n}\to \{0,1\}$ { $displaystyle$ x \ $in \ 0$ , 1 \ 0 , 1 \ } } n } } $x\in \{0,1\}^{n}$ . $f:\{0,1\}^{n}\to \{0,1\}$ 。쿼리는 입력의 비트( $\$ $displaystyle$ $x_{i$ 에 대응하며 $f(x)$ 은 f $)입니다.$ 각 쿼리는 이전 쿼리에 의존할 수 있습니다.복잡도 측정이라고 불리는 다중 복잡도 개념을 수용하여 고려할 수 있는 의사결정 트리를 사용하는 계산 모델에는 여러 가지 유형이 있습니다.

결정론적 결정 트리

Decision Tree 출력이 $f(x)$ ( $f(x)$ $){$ $displaystyle$ f ( $x$ $f(x)$ $displaystyle$ \ $in$ \ { $0$ , $1$ \ $x\in \{0,1\}^{n}$ $n$ 의 $x\in \{0,1\}^{n}$ , Decision Tree 는 " $computing$ " f {\ $displaystyle$ f $f$ 로 표시됩니다.트리의 깊이는 리프에 도달하여 결과를 얻기 전에 발생할 수 있는 최대 쿼리 수입니다. $D(f)$ ) { $displaystyle$ D $(f$ f{ $displaystyle$ f $}$ 의 $f$ 결정론적 의사결정 트리의 복잡도는 f{ $displaystyle$ f $f$ 를 $f$ 하는 모든 결정론적 의사결정 트리 중 가장 작다.

무작위 의사결정 트리

랜덤화 의사결정 트리를 정의하는 한 가지 방법은 트리에 노드를 추가하는 것입니다.각 노드를 $p_{i}$ $(\$ style $p_{i$ 에 의해 제어합니다.또 다른 동등한 정의는 결정론적 의사결정 트리에 대한 분포로 정의하는 것입니다.이 두 번째 정의에 기초하여 랜덤화 트리의 복잡도는 기본 분포를 지원하는 모든 트리 중 가장 큰 깊이로 정의된다. $R_{2}(f)$ 2 $R_{2}(f)$ ( $R_{2}(f)$ ) { $displaystyle R_{2$ } $(f)$ $x\in \{0,1\}^{n}$ 는 $R_{2}(f)$ $f(x)$ f $f(x)$ ( $f(x)$ ) { $displaystyle$ f $(x)}$ { 0 $x\in \{0,1\}^{n}$ , $x\in \{0,1\}^{n}$ {\ $displaystyle$ x $\in \0$ , 1 \ } n {\ displaystyle f $(x$ )} {\ $x\in \{0,1\}^{n}$ displaystyle f(x} n } n $x\in \{0,1\}^{n}$ } n $x\in \{0,1\}^{n}$ e e e , $2/3$ , e $2/3$ ）。

$R_{2}(f)$ 2 $R_{2}(f)$ ( $R_{2}(f)$ $)\displaystyle R_{2}(f)}$ 은 $R_{2}(f)$ (는) 경계가 있는 양면 오차로 결과가 부정확할 수 있기 때문에 몬테카를로 무작위 의사결정 트리 복잡도로 알려져 있다.라스베이거스 의사결정 트리 $R_{0}(f)$ R $R_{0}(f)$ 0 ( $R_{0}(f)$ $){displaystyle R_{0}(f)}$ 은 $R_{0}(f)$ 정확해야 하는 의사결정 트리의 예상 깊이를 측정합니다(즉, 오류 0). $R_{1}(f)$ R $R_{1}(f)$ ( f $)\displaystyle R_{$ 1}(f $R_{1}(f)$ 로 $표시$ 되는 일방적인 경계 오류 버전도 있습니다.

비결정론적 결정 트리

함수의 비결정론적 의사결정 트리의 복잡성은 일반적으로 해당 함수의 증명서 복잡성으로 알려져 있습니다.비결정론적 알고리즘이 함수를 확실하게 평가하기 위해 검토해야 하는 입력 비트 수를 측정합니다.

공식적으로x {\ $displaystyle$ x $}$ 에서 $x$ f {\ $displaystyle$ f $}$ 의 $f$ 인증 $S\subset [n]$ 복잡도는 모든 $y\in \{0,1\}^{n}$ $S\subset [n]$ { $y\in \{0,1\}^{n}$ , 1 $y\in \{0,1\}^{n}$ $y\in \{0,1\}^{n}$ ${\$ $S\subset [n]$ y $\in$ \ ${ 0$ , 1 \ }^{ $n$ $y\in \{0,1\}^{n}$ $y_{i}=x_{i}$ y $=$ $y_i}$ 의 최소 $S\subset [n]$ 집합 $크기$ 이다. $f(y)=f(x)$ $displaystyle$ i $\in$ S $\$ f $i\in S$ $f(y)=f(x)$ $=$ $)$ {\ $displaystyle f($ y)= $f(x$ f{\ $displaystyle$ f $}$ 의 $f$ 증명서의 복잡도는 $모든$ x {\ $displaystyle$ x $x$ 의 증명서의 복잡도 중 최대입니다.검증자가 2/3 확률로 정확해야 하는 유사한 개념은 $RC(f)$ $RC(f)$ ( $RC(f)$ f ) $RC(f)$ \ $display style$ RC ( $f$ ) $RC(f)$

양자 결정 트리

양자 결정 트리 $Q_{2}(f)$ $Q_{2}(f)$ $f$ ) {\displaystyle $Q_{2}(f)}$ 는 $Q_{2}(f)$ $x\in \{0,1\}^{n}$ x $x\in \{0,1\}^{n}$ { { $x\in \{0,1\}^{n}$ $x\in \{0,1\}^{n}$ } $x\in \{0,1\}^{n}$ {\ $displaystyle x\{0,1\n$ 에 $2/3$ 최소 $2/3$ 2 $/3$ 의 $2/3$ 확률로 $f(x)$ ( $)$ { $displaystyle$ f $($ $x)}$ 결과를 제공하는 $f(x)$ 가장 낮은 양자 결정 트리의 깊이이다. $Q_{E}(f)$ E ( $Q_{E}(f)$ ) { $displaystyle Q$ _ { $E$ （ $f$ ） $Q_{E}(f)$ is decision $f(x)$ 、 f ( f ) is 、 $f(x)$ f () $f(x)$ ( x $f(x)$ ) $f(x)$ （ $displaystyle$ f ( $x$ ) （ x ) f $f(x)$ f f f f （ f ） ( ( ( f f f f f q in in in in in in in in in in in1 ( f { $displaystyle$ f））의 $f$ 깊이로 정의됩니다. $Q_{2}(f)$ 2 $)$ { $displaystyle Q_{2}(f)}$ 및 $Q_{E}(f)$ $)$ { $displaystyle Q_{E}(f)}$ 는 $Q_{2}(f)$ $Q_{E}(f)$ 양자 결정 트리의 직접 정의가 기존의 경우보다 더 복잡하기 때문에 일반적으로 양자 질의 복잡성으로 알려져 있다.랜덤화 경우와 마찬가지로 Q $)$ { $displaystyle Q_{0}(f)}$ 및 $Q_{0}(f)$ $Q_{1}(f)$ 1 $)$ { $displaystyle Q_{1}(f$ 을(를) $Q_{0}(f)$ 합니다.

이러한 개념들은 전형적으로 정도와 근사 정도의 개념에 의해 제한된다.f{\ $displaystyle$ f $\deg(f)$ $deg$ $)$ ( $f)$ {\displaystyle $\displaystyle f$ $}$ 의 정도는 모든 $\deg(f)$ $x\in \{0,1\}^{n}$ { $x\in \{0,1\}^{n}$ 0 , $x\in \{0,1\}^{n}$ } $x\in \{0,1\}^{n}$ $displaystyle$ x\in {0 , n $}에$ 대해 f $f(x)=p(x)$ $=$ $(x)$ 를 $f(x)=p(x)$ 만족시키는 $p$ 모든 $다항식$ p(\ $displaystyle$ p)의 최소도입니다. $deg$ ${\widetilde {\deg }}(f)$ ( ${\widetilde {\deg }}(f)$ ) { $displaystyle$ $f$ $f$ } $style$ [ 0 , 1 / 3 $]$ { $displaystyle$ p ( x $p(x)\in [0,1/3]$ ) $p(x)\in [0,1/3]$ [ $p(x)\in [0,1/3]$ , $1$ / $3$ } { $f(x)=0$ p( $x$ $f(x)=0$ )} $f(x)=0$ $p(x)\in [0,1/3]$ $f(x)=0$ $= display style$ fx } ${\widetilde {\deg }}(f)$ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ 0 = 0 $f(x)=0$ = 0 ( f ( fx ) styledisplay style f ( fx )를 $p(x)\in [0,1/3]$ $f(x) = 0$ $p(x)\in [0,1/3]$ 시키는 $p$ $p$ 의 최소도입니다. $p(x)\in [2/3,1]$ $f(x)=1$ $p(x)\in [2/3,1]$ , $]($ $f(x)=1$ ) $f(x)=1$ $(\displaystyle$ f $(x$ ) $=$ )일 $p(x)\in [2/3,1]$ 때({ $displaystyle$ p $(x)\in [2/3,1])$

Beals $Q_{0}(f)\geq \deg(f)/2$ 에서는 $Q_{0}(f)\geq \deg(f)/2$ Q $Q_{0}(f)\geq \deg(f)/2$ ( f $Q_{0}(f)\geq \deg(f)/2$ ) $Q_{0}(f)\geq \deg(f)/2$ $Q_{0}(f)\geq \deg(f)/2$ ( $Q_{0}(f)\geq \deg(f)/2$ f ) $Q_{0}(f)\geq \deg(f)/2$ / $Q_{0}(f)\geq \deg(f)/2$ ( { $displaystyle$ Q _ { $0$ $Q_{0}(f)\geq \deg(f)/2$ } ( $f$ ) \ $deg ( f$ ) / $Q_{2}(f)\geq {\widetilde {\deg }}(f)/2$ ( $Q_{2}(f)\geq {\widetilde {\deg }}(f)/2$ ) $Q_{2}(f)\geq {\widetilde {\deg }}(f)/2$ 2 $Q_{2}(f)\geq {\widetilde {\deg }}(f)/2$ ( $display style$ Q _ { $2}$ ( f ) \ $widetilde }$ f / $2$ ( 2 $Q_{2}(f)\geq {\widetilde {\deg }}(f)/2$ ^[9]가 $Q_{0}(f)\geq \deg(f)/2$ $Q_{0}(f)\geq \deg(f)/2$ 되었습니다.

부울 함수 복잡도 측정값 간의 관계

이는 모든 $n개$ 의 {\ $displaystyle$ n $}$ 비트 $n$ 부울 $함수$ f {\ $displaystyle$ f $f$ $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ ( $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ ) $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ 2 $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ ( $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ ) $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ 、 R 1 $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ ( $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ ) $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ 0 $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ ( $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ ) $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ 、 $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ ( $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ ) $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ 、 n $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ { $displaystyle$ Q $_$ ${ 2 ( f$ ) （ f )\ $le it$ it it it for for for for for for for f f f f f f f f f f f f f f f f f f 。 $Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n$ {\ $displaystyle Q_{2}($ f)\ $leq Q_{0}($ f)\ $leq D(f$ )\ $leq$ n $Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n$ 쿼리 복잡성 분야의 주요 목표는 역방향으로 최적의 상한을 찾는 것입니다 $.$

이러한 유형의 쿼리 복잡성은 모두 다항식으로 관련되어 있습니다.보다 블럼 회장과 Impagliazzo,[10]Hartmanis과 Hemachandra,[11]과 Tardos[12]독립적으로 D(f)≤ 미국의 0(f)2{\displaystyle D(f)\leq R_{0}(f)^{2}}. 노암 니산은 몬테 카를로는 또한 polynomially 결정론적 의사 결정 분지도 복잡성과 관련된 의사 결정 분지도 복잡성 D(f))O(미국의 2한가지 발견을 발견했다. (f)3 ){\displaystyle D(f)=O(R_{2}(f)^{3})}(니산 또한 D(f 보여 줬다))O(미국의 1(f)2){\displaystyle D(f)=O(R_{1}(f)^{2})}.)한 손아귀에 관계가 몬테 카를로, 라스 베이거스 모델들 사이에 알려져 있:미국의 0(f)).[13]O(미국의 2(f)2로그 ⁡ R2(f)){\displaystyle R_{0}(f)=O(R_{2}(f)^{2}\log R_{.2}(f $)$ ^[14]). 이 관계는 다산술 ^[15]인수까지 최적입니다.양자결정목의 복잡도는 D $D(f)=O(Q_{2}(f)^{4})$ ( $D(f)=O(Q_{2}(f)^{4})$ $D(f)=O(Q_{2}(f)^{4})$ ( $Q$ 2 ( $D(f)=O(Q_{2}(f)^{4})$ 4 $)$ {{ $style$ D (f $) =$ O ( $Q_{2} ($ f)^{4 $D(f)=O(Q_{2}(f)^{4})$ 이며,^[16]^[15] 이 바운드는 엄격하다.미드랴니스는 D $D(f)=O(Q_{0}(f)^{3})$ $=$ $D(f)=O(Q_{0}(f)^{3})$ $D(f)=O(Q_{0}(f)^{3})$ ( $D(f)=O(Q_{0}(f)^{3})$ ) $D(f)=O(Q_{0}(f)^{3})$ ) {{ $displaystyle$ D $(f$ )= $O(Q_{0}(f)^{$ 3 $D(f)=O(Q_{0}(f)^{3})$ ^[17]^[18]를 나타내며, Beals ^[9]등에 의한 사분위 결합을 개선하였다.

이러한 다항식 관계는 전체 부울 함수에 대해서만 유효합니다.도메인이 $\{0,1\}^{n}$ { $\{0,1\}^{n}$ , $\{0,1\}^{n}$ $\{0,1\}^{n}$ { { $displaystyle$ \ { $0$ , 1 \ }^{ $n$ $\{0,1\}^{n}$ }인 부분 부울 함수의 $Q_{0}(f)$ 0 $Q_{0}(f)$ ( $Q_{0}(f)$ f ) { $displaystyle$ $Q_{0}(f)$ Q _ $0$ ( f ) d $Q_{0}(f)$ $D$ ( f ) $D(f)$ d $D(f)$ d d $D(f)$ f ) $D(f)$ entialentialentialentialentialentialentialentialential q q q q qationationationationationationationationationationationationationationationationationationationationationationationationationationationation ationationationationationationationationationationationationationationationationationationationationationationationationationationationationationationationationationationation

감도 추측

부울 $f:\{0,1\}^{n}\to \{0,1\}$ f : $f:\{0,1\}^{n}\to \{0,1\}$ { $f:\{0,1\}^{n}\to \{0,1\}$ , $f:\{0,1\}^{n}\to \{0,1\}$ $f:\{0,1\}^{n}\to \{0,1\}$ $f:\{0,1\}^{n}\to \{0,1\}$ $f:\{0,1\}^{n}\to \{0,1\}$ { $f:\{0,1\}^{n}\to \{0,1\}$ , $f:\{0,1\}^{n}\to \{0,1\}$ $}$ { { $displaystyle$ f $:\$ { $0$ , $1$ \ } { $n$ } \ $to$ \0 , $1$ \ $f:\{0,1\}^{n}\to \{0,1\}$ }의 경우 f의 $f$ $f$ $감도는$ x $\ display$ $style$ 의 $fstyle$ 에 $대한$ $f$ 의 $f$ $최대$ 감도로 정의됩니다 $x$ f $f(x)$ ( $f(x)$ ) $f(x)$ { $displaystyle$ f $(x$ 의 값을 변경하는 x{\ $displaystyle$ x}의 $x$ 단일 비트 변경 수. 민감도는 부울 함수 분석의 전체 영향 개념과 관련이 있으며 $전체$ x {\ $displaystyle$ x $x$ 의 평균 민감도와 동일합니다.

민감도 추측은 민감도가 쿼리 복잡도와 다항식으로 관련되어 있다는 추측이다. 즉 $,$ $모든$ f{\ $displaystyle$ f $f$ $D(f)=O(s(f)^{c})$ ( $D(f)=O(s(f)^{c})$ ) $D(f)=O(s(f)^{c})$ $D(f)=O(s(f)^{c})$ ( $D(f)=O(s(f)^{c})$ ( $D(f)=O(s(f)^{c})$ ) $D(f)=O(s(f)^{c})$ \ $displaystyle$ D ( f ) $= O$ ( f ) $s(f)=O(D(f)^{c'})$ ( ) （ displaystyle D ( $f$ ) = O ( $s(f)=O(D(f)^{c'})$ ) $D(f)=O(s(f)^{c})$ $（$ $s(f)=O(D(f)^{c'})$ ) ）（ f $s(f)=O(D(f)^{c'})$ ）。 $tyle$ s $(f)=O(D(f)^{c$ 단순한 인수를 통해 s $s(f)\leq D(f)$ ( $s(f)\leq D(f)$ D ( $)\display$ s $(f)\leq$ D $(f$ 을 보여줄 수 있으므로 특히 추측은 감도 하한을 찾는 데 관심이 있다.앞에서 설명한 모든 복잡도 척도는 다항식으로 관련되어 있기 때문에 정확한 복잡도 척도의 유형은 관련이 없다.단, 이것은 일반적으로 감도와 블록 감도를 관련짓는 질문으로 표현됩니다.

$bs(f)$ s $bs(f)$ ( $bs(f)$ ) { $displaystyle$ bs ( $bs(f)$ f ) { displaystyle f $}$ 의 블록 $bs(f)$ 감도는 x { $displaystyle$ x $x$ 의 f ${\$ $displaystyle$ f $}$ 의 $f$ $최대$ 블록 감도로 정의됩니다.x{\ $displaystyle$ x $}$ 에서 $x$ f {\ $displaystyle$ f $}$ 의 $f$ 블록 감도는 S 1, $S_{1},\ldots ,S_{t}\subset [n]$ …, $S_{1},\ldots ,S_{t}\subset [n]$ t $S_{1},\ldots ,S_{t}\subset [n]$ [ n $S_{1},\ldots ,S_{t}\subset [n]$ ](\ $displaystyle$ $S_{i}$ ${1$ },\ $ldots, S_{$ t $S_{i}$ $[n$ ])의 $S_{1},\ldots ,S_{t}\subset [n]$ 최대t(\ $displaystyle$ style t $)$ 입니다 $t$ $.$ $S_{i}$ { $display style$ S _ { $i$ } 에 $S_{i}$ $대응하는ystyle$ x 를 지정하면 $x$ f $f(x)$ ( $f(x)$ $){$ $display$ f $(x$ ^[13] 의 $f(x)$ 이 변경됩니다.

블록 감도는 더 많은 서브셋 $s(f)\leq bs(f)$ 에 대해 s $s(f)\leq bs(f)$ ( $s(f)\leq bs(f)$ ) $s(f)\leq bs(f)$ b $s(f)\leq bs(f)$ s ( $s(f)\leq bs(f)$ $){$ $displaystyle$ s ( $f$ )\ $leq bs$ ( $s(f)\leq bs(f)$ $bs(f)\leq D(f)=O(bs(f)^{4})$ ). $s(f)\leq bs(f)$ 또한 블록 감도는 앞서 논의한 복잡성 측정과 다항식적으로 관련되어 있습니다. 예를 들어 블록 감도를 소개하는 Nisan의 $bs(f)\leq D(f)=O(bs(f)^{4})$ 은 $bs(f)\leq D(f)=O(bs(f)^{4})$ ( f ) $bs(f)\leq D(f)=O(bs(f)^{4})$ $bs(f)\leq D(f)=O(bs(f)^{4})$ ( f ) $bs(f)\leq D(f)=O(bs(f)^{4})$ $bs(f)\leq D(f)=O(bs(f)^{4})$ ) $bs(f)\leq D(f)=O(bs(f)^{4})$ ( f ) f ) o s ( f ) f ) $bs(f)\leq D(f)=O(bs(f)^{4})$ \ $displaystyle$ bs $(f)\leq$ D $(f)=O(bs(f)^{$ 4 $bs(f)\leq D(f)=O(bs(f)^{4})$ ^[13] 따라서 1992년 Sisan 및 Sisan의 $일부$ c $\display c$ $bs(f)=O(s(f)^{c})$ $bs(f)=O(s(f)^{c})$ $=$ $f$ $\style$ bs( $f)= O($ c)^{c $bs(f)=O(s(f)^{c})$ 에 대해 감도 추측을 나타낼 수 있다 $.$ 이는 1995년 루빈스타인이 감도와 ^[20]블록 감도 사이의 2차 분리를 보여주었기 때문에 엄격할 것이다.

추측이 처음 제기된 지 27년이 지난 2019년 7월, 에모리 대학의 Hao Huang은 b $bs(f)=O(s(f)^{4})$ ( $bs(f)=O(s(f)^{4})$ ) $=$ ( $bs(f)=O(s(f)^{4})$ ( $bs(f)=O(s(f)^{4})$ ) $)$ {{ $displaystyle$ bs (f)= $O$ ( $s (f)^$ 4 $bs(f)=O(s(f)^{4})$ ^[21]라는 것을 보여주며 민감도 추측을 입증했다.민감도 추측에 대한 이전 진행이 ^[22]^[23]제한되었을 때 두 페이지에 걸쳐 이 진술을 입증하는 이 증거는 매우 간결하다.

알려진 결과의 요약

2020년 10월^[16] 현재 복잡성 조치를 위한 가장 잘 알려진 분리

	$D$	$R_{0}$	$R_{2}$	$C$	$RC$	$\[디스플레이 스타일 bs$	$디스플레이 스타일$	$Q_{0}$	$\displaystyle \displays }$	$Q$	$(*disteryle$
$D$		2	2, 3	2	2, 3	2, 3	3, 6	2, 3	2, 3	4	4
$R_{0}$	1		2	2	2, 3	2, 3	3, 6	2, 3	2, 3	3, 4	4
$R$	1	1		2	2, 3	2, 3	3, 6	1.5, 3	2, 3	3, 4	4
$C$	1	1	1, 2		2	2	2.22, 5	1.15, 3	1.63, 3	2, 4	2, 4
$RC$	1	1	1	1		1.5, 2	2, 4	1.15, 2	1.63, 2	2	2
$\[디스플레이 스타일 bs$	1	1	1	1	1		2, 4	1.15, 2	1.63, 2	2	2
$디스플레이 스타일$	1	1	1	1	1	1		1.15, 2	1.63, 2	2	2
$Q_{0}$	1	1.33, 2	1.33, 3	2	2, 3	2, 3	3, 6		2, 3	2, 4	4
$\displaystyle \displays }$	1	1.33, 2	1.33, 2	2	2	2	2	1		2	2
$Q$	1	1	1	2	2, 3	2, 3	3, 6	1	2, 3		4
$(*disteryle$	1	1	1	2	2	2	2	1	1	1

이 표에는 부울 함수 복잡도 측도 간의 분리에 대한 결과가 요약되어 있습니다.복잡도 척도는 결정론적, 제로 오류 무작위화, 양면 오류 무작위화, 인증서, 무작위 인증서, 블록 민감도, 민감도, 정확한 양자, 정도, 양자 및 대략적인 정도 복잡도이다.

$({displaystyle$ A $}$ - 행 $A$ 및 $B$ ({ $displaystyle$ B $A(f)=O(B(f)^{k})$ - 열의 $B$ 숫자는 $지수$ c({ $displaystyle$ c $c$ 의 경계를 나타냅니다. 이는 모든f에 $대해$ A $A(f)=O(B(f)^{k})$ $A(f)=O(B(f)^{k})$ $O$ k $({displaystyle$ A $(f$ ) = $O(f)$ k $)$ 의 $k$ $A(f)=O(B(f)^{k})$ 최소값입니다.r 예: $D번째$ 행과 s번째 열의 엔트리는 "3, 6"이므로 D $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ ( $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ ) $=$ $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ ( $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ ( $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ ) $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ + $o$ ( 1 $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ ){ $display D$ ( f ) = O ( \ $operatorname$ { $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ s $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ } ( f ){ 6 $+ o$ ( $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ 1 } )\ $display$ $style$ f $f$ $。$ $(\operatorname {s}(g)^{3-o($ 1 $D(g)=\Omega (\operatorname {s} (g)^{3-o(1)})$

「」를 참조해 주세요.

레퍼런스

^ Jr, Lester R. Ford; Johnson, Selmer M. (1959-05-01). "A Tournament Problem". The American Mathematical Monthly. 66 (5): 387–389. doi:10.1080/00029890.1959.11989306. ISSN 0002-9890.
^ ^a ^b Introduction to algorithms. Cormen, Thomas H. (Third ed.). Cambridge, Mass.: MIT Press. 2009. ISBN 978-0-262-27083-0. OCLC 676697295.{{cite book}}: CS1 유지보수: 기타 (링크)
^ Rabin, Michael O. (1972-12-01). "Proving simultaneous positivity of linear forms". Journal of Computer and System Sciences. 6 (6): 639–650. doi:10.1016/S0022-0000(72)80034-5. ISSN 0022-0000.
^ Reingold, Edward M. (1972-10-01). "On the Optimality of Some Set Algorithms". Journal of the ACM. 19 (4): 649–659. doi:10.1145/321724.321730. ISSN 0004-5411. S2CID 18605212.
^ Preparata, Franco P. (1985). Computational geometry : an introduction. Shamos, Michael Ian. New York: Springer-Verlag. ISBN 0-387-96131-3. OCLC 11970840.
^ Ben-Or, Michael (1983-12-01). "Lower bounds for algebraic computation trees". Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. STOC '83. New York, NY, USA: Association for Computing Machinery: 80–86. doi:10.1145/800061.808735. ISBN 978-0-89791-099-6. S2CID 1499957.
^ Dobkin, David; Lipton, Richard J. (1976-06-01). "Multidimensional Searching Problems". SIAM Journal on Computing. 5 (2): 181–186. doi:10.1137/0205015. ISSN 0097-5397.
^ Michael Steele, J; Yao, Andrew C (1982-03-01). "Lower bounds for algebraic decision trees". Journal of Algorithms. 3 (1): 1–8. doi:10.1016/0196-6774(82)90002-5. ISSN 0196-6774.
^ ^a ^b Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). "Quantum lower bounds by polynomials". Journal of the ACM. 48 (4): 778–797. arXiv:quant-ph/9802049. doi:10.1145/502090.502097. S2CID 1078168.
^ Blum, M.; Impagliazzo, R. (1987). "Generic oracles and oracle classes". Proceedings of 18th IEEE FOCS. pp. 118–126.
^ Hartmanis, J.; Hemachandra, L. (1987), "One-way functions, robustness, and non-isomorphism of NP-complete sets", Technical Report DCS TR86-796, Cornell University
^ Tardos, G. (1989). "Query complexity, or why is it difficult to separate NP^A ∩ coNP^A from P^A by random oracles A?". Combinatorica. 9 (4): 385–392. doi:10.1007/BF02125350. S2CID 45372592.
^ ^a ^b ^c Nisan, N. (1989). "CREW PRAMs and decision trees". Proceedings of 21st ACM STOC. pp. 327–335.
^ Kulkarni, R.와 Tal, A.Fractional Block Sensitivity에 대하여.계산 복잡성에 관한 전자 토론회(ECCC)제20권 2013년
^ ^a ^b Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troy; Santha, Miklos; Smotrovs, Juris (2017-09-04). "Separations in Query Complexity Based on Pointer Functions". Journal of the ACM. 64 (5): 32:1–32:24. arXiv:1506.04719. doi:10.1145/3106234. ISSN 0004-5411. S2CID 10214557.
^ ^a ^b Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay (2020-10-23). "Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem". arXiv:2010.12629 [quant-ph].
^ Midrijanis, Gatis (2004), "Exact quantum query complexity for total Boolean functions", arXiv:quant-ph/0403168
^ Midrijanis, Gatis (2005), "On Randomized and Quantum Query Complexities", arXiv:quant-ph/0501142
^ Nisan, Noam; Szegedy, Mario (1992-07-01). "On the degree of Boolean functions as real polynomials". Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing. STOC '92. Victoria, British Columbia, Canada: Association for Computing Machinery: 462–467. doi:10.1145/129712.129757. ISBN 978-0-89791-511-3. S2CID 6919144.
^ Rubinstein, David (1995-06-01). "Sensitivity vs. block sensitivity of Boolean functions". Combinatorica. 15 (2): 297–299. doi:10.1007/BF01200762. ISSN 1439-6912. S2CID 41010711.
^ Huang, Hao (2019). "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture". Annals of Mathematics. 190 (3): 949–955. arXiv:1907.00847. doi:10.4007/annals.2019.190.3.6. ISSN 0003-486X. JSTOR 10.4007/annals.2019.190.3.6. S2CID 195767594.
^ Klarreich, Erica. "Decades-Old Computer Science Conjecture Solved in Two Pages". Quanta Magazine. Retrieved 2019-07-26.
^ Hatami, Pooya; Kulkarni, Raghav; Pankratov, Denis (2011-06-22). "Variations on the Sensitivity Conjecture". Theory of Computing. 1: 1–27. doi:10.4086/toc.gs.2011.004. ISSN 1557-2862. S2CID 6918061.

조사

Buhrman, Harry; de Wolf, Ronald (2002), "Complexity Measures and Decision Tree Complexity: A Survey" (PDF), Theoretical Computer Science, 288 (1): 21–43, doi:10.1016/S0304-3975(01)00144-X

[1] Jr, Lester R. Ford; Johnson, Selmer M. (1959-05-01). "A Tournament Problem". The American Mathematical Monthly. 66 (5): 387–389. doi:10.1080/00029890.1959.11989306. ISSN 0002-9890.

[CLRS-2] Introduction to algorithms. Cormen, Thomas H. (Third ed.). Cambridge, Mass.: MIT Press. 2009. ISBN 978-0-262-27083-0. OCLC 676697295.{{cite book}}: CS1 유지보수: 기타 (링크)

[3] Rabin, Michael O. (1972-12-01). "Proving simultaneous positivity of linear forms". Journal of Computer and System Sciences. 6 (6): 639–650. doi:10.1016/S0022-0000(72)80034-5. ISSN 0022-0000.

[4] Reingold, Edward M. (1972-10-01). "On the Optimality of Some Set Algorithms". Journal of the ACM. 19 (4): 649–659. doi:10.1145/321724.321730. ISSN 0004-5411. S2CID 18605212.

[5] Preparata, Franco P. (1985). Computational geometry : an introduction. Shamos, Michael Ian. New York: Springer-Verlag. ISBN 0-387-96131-3. OCLC 11970840.

[6] Ben-Or, Michael (1983-12-01). "Lower bounds for algebraic computation trees". Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. STOC '83. New York, NY, USA: Association for Computing Machinery: 80–86. doi:10.1145/800061.808735. ISBN 978-0-89791-099-6. S2CID 1499957.

[7] Dobkin, David; Lipton, Richard J. (1976-06-01). "Multidimensional Searching Problems". SIAM Journal on Computing. 5 (2): 181–186. doi:10.1137/0205015. ISSN 0097-5397.

[8] Michael Steele, J; Yao, Andrew C (1982-03-01). "Lower bounds for algebraic decision trees". Journal of Algorithms. 3 (1): 1–8. doi:10.1016/0196-6774(82)90002-5. ISSN 0196-6774.

[Beals-9] Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). "Quantum lower bounds by polynomials". Journal of the ACM. 48 (4): 778–797. arXiv:quant-ph/9802049. doi:10.1145/502090.502097. S2CID 1078168.

[BlumImpagliazzo_1995-10] Blum, M.; Impagliazzo, R. (1987). "Generic oracles and oracle classes". Proceedings of 18th IEEE FOCS. pp. 118–126.

[HartmanisHemachandra-11] Hartmanis, J.; Hemachandra, L. (1987), "One-way functions, robustness, and non-isomorphism of NP-complete sets", Technical Report DCS TR86-796, Cornell University

[Tardos-12] Tardos, G. (1989). "Query complexity, or why is it difficult to separate NP^A ∩ coNP^A from P^A by random oracles A?". Combinatorica. 9 (4): 385–392. doi:10.1007/BF02125350. S2CID 45372592.

[Nisan-13] Nisan, N. (1989). "CREW PRAMs and decision trees". Proceedings of 21st ACM STOC. pp. 327–335.

[KT13-14] Kulkarni, R.와 Tal, A.Fractional Block Sensitivity에 대하여.계산 복잡성에 관한 전자 토론회(ECCC)제20권 2013년

[ABBLSS17-15] Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troy; Santha, Miklos; Smotrovs, Juris (2017-09-04). "Separations in Query Complexity Based on Pointer Functions". Journal of the ACM. 64 (5): 32:1–32:24. arXiv:1506.04719. doi:10.1145/3106234. ISSN 0004-5411. S2CID 10214557.

[ABKRT-16] Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay (2020-10-23). "Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem". arXiv:2010.12629 [quant-ph].

[Midrijanis-17] Midrijanis, Gatis (2004), "Exact quantum query complexity for total Boolean functions", arXiv:quant-ph/0403168

[Midrijanis2-18] Midrijanis, Gatis (2005), "On Randomized and Quantum Query Complexities", arXiv:quant-ph/0501142

[NisanSzegedy-19] Nisan, Noam; Szegedy, Mario (1992-07-01). "On the degree of Boolean functions as real polynomials". Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing. STOC '92. Victoria, British Columbia, Canada: Association for Computing Machinery: 462–467. doi:10.1145/129712.129757. ISBN 978-0-89791-511-3. S2CID 6919144.

[Rub95-20] Rubinstein, David (1995-06-01). "Sensitivity vs. block sensitivity of Boolean functions". Combinatorica. 15 (2): 297–299. doi:10.1007/BF01200762. ISSN 1439-6912. S2CID 41010711.

[Huang-21] Huang, Hao (2019). "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture". Annals of Mathematics. 190 (3): 949–955. arXiv:1907.00847. doi:10.4007/annals.2019.190.3.6. ISSN 0003-486X. JSTOR 10.4007/annals.2019.190.3.6. S2CID 195767594.

[22] Klarreich, Erica. "Decades-Old Computer Science Conjecture Solved in Two Pages". Quanta Magazine. Retrieved 2019-07-26.

[HKP-23] Hatami, Pooya; Kulkarni, Raghav; Pankratov, Denis (2011-06-22). "Variations on the Sensitivity Conjecture". Theory of Computing. 1: 1–27. doi:10.4086/toc.gs.2011.004. ISSN 1557-2862. S2CID 6918061.

[1]

[2]

[4]

[3]

[5]

[6]

[7]

[8]

[9]

[14]

[15]

[16]

[17]

[18]

[13]

[20]

[21]

[22]

[23]

Search

의사결정 트리 모델

네임스페이스

더

목차

비교 트리 및 정렬 하한

선형 및 대수적 결정 트리