지수 시간 가설

지수 시간 가설은 계산 복잡도 이론에서 Impaglizo & Paturi(1999)가 공식화한 검증되지 않은 계산 경도 가정입니다.3-CNF 부울 공식의 만족도는 하위 지수 시간인 $n)$ {\$displaystyle$2^{$(n)}$에서 해결할 수 없음을 명시합니다$.$ 더 정확하게 말하면,이 가설의 일반적인 형태는 3 > ${\displaystyle s_{3}$ > $0}$의 존재를 주장합니다. 따라서 이 문제를 올바르게 해결하는 모든 알고리즘은 최소 $2초$ ${\displaystyle {3_{}}^{}}$의 ${\displaystyle {{}_{}}^{}}$을 필요로 합니다$.$$${\$displaystyle$ 2$^{s_{3}n}}.$지수 시간 가설이 참이면 P가 NP ≠임을 의미하지만 더 강력한 문장입니다.이것은 많은 계산 문제가 하위 지수 시간 알고리즘을 가지고 있으면 모두가 복잡하다는 의미에서 복잡성이 동일하다는 것을 의미하며, 이러한 문제에 대해 알려진 많은 알고리즘이 최적 또는 거의 최적의 시간 복잡성을 가지고 있다는 것을 의미합니다.^[1]

정의.

$k{\displaystyle }$ ${\displaystyle k}$ -SAT$$ 문제는 해당 문제에 대한 입력이 절당 최대 $k개$의 ${\displaystyle$ k$}개$의 변수가$$ 있는 연결 정규 형식(즉, 변수 의 및 해당 부정)의 부울 식인 부울 만족성 문제의 버전입니다.변수에 부울 값을 할당하여 이 식을 참으로 만들 수 있는지 여부를 확인하는 것이 목표입니다. 2-SAT에는 선형 시간 알고리즘이 있지만, 더 큰 $k{\displaystyle }${\$displaystyle k}$에 대한 알려진 모든 알고리즘은 $k{\displaystyle }$ ${\displaystyle k}$에 따라 지수 함수의 기본값을 사용하여 지수 시간이 걸립니다$$$.$ 예를 들어, 보행SAT 확률 알고리즘은 평균 시간 $내$에 k ${\displaystyle k}$ -SAT를 해결할 수 있습니다.

여기서 $n{\displaystyle }$ ${\displaystyle n}$은(는) 주어진 $k{\displaystyle }$ ${\displaystyle k}$ -SAT 인스턴스의 변수 수입니다.^[2]$각$ 정수 $k$ ≥ 3 ${\displaystyle$ k$\backslash$geq 3}에 대해 k ${\$displaystyle$$k} -SAT를 ${\displaystyle {{}_{}}^{}}$2${\displaystyle {\mathrm{sk}}^{}}$n +$$o (n) ${\displaystyle$2^{$k}$n + o(n)}에 해결할$$수 $있도록$ $sk$ {\$displaystyle$ s_{k$}$ n (n)}를 가장 작은 수로$$합니다.일련의 더 나은 알고리즘이 시간 한계에서 지수 증가량이 상응하게 작을 경우 이 최소값은 존재하지 않을 수 있습니다. 이 경우 ${\displaystyle {sk}_{}}$ ${\displaystyle s_{k}$를 k ${\$displaystyle$$k} -SAT가 ${\displaystyle {시간}^{}}$ ${\displaystyle O^{}(}$2$$δ n)${\$displaystyle \delta }에서 풀 수 있는$$실수$$δ {\displaystyle s_{k}의 최소값으로 정의합니다.$eltan})}.$k가$큰$ {\$displaystyle$$$k$}$의 문제는 이보다 더 쉽게 해결할 수 없기 때문에, 이 $숫자들$은 ${\displaystyle s_{}}$ 3${\displaystyle {}_{}}$≤ ${\displaystyle s_{}}$ 4${\displaystyle {}_{}}$≤$$$⋯$ {\$displaystyle$ s_{$3}\leq$ s_${4$}\leq$$\cdots}로 정렬되며, 이는 보행 때문입니다.SAT 그들은 많아야 합니다.지수 시간 가설은 그들 모두가 0이 아니라는 추측 또는 그들 중 가장 작은 ${\displaystyle {s3\mathrm{}}_{}}$ ${\$이$$0이 아니라는 추측입니다.^[1]

일부 출처에서는 지수 시간 가설을 ${\displaystyle {2o(n)}^{}}$ 시간 ${\$에서 3-SAT를 풀 수 없다는 약간 약한 문장으로 정의합니다$.$ ${\displaystyle {2o(n)}^{}}$ 시간 ${\$에서 3-SAT를 풀 수 있는 알고리즘이 존재한다면$$${\displaystyle {s3\mathrm{}}_{}}$ ${\$은 0과 같습니다$$.그러나 0으로 향하는 일련의 ${\displaystyle {숫자}_{}}$δ i ${\displaystyle \$delta _{i}}에 대해 각각 실행 $시간$ O${\displaystyle ({}^{}}$δ in $){\displaystyle$O($2^{\delta$_{i}n})}를 갖는 3-SAT 알고리즘이 있을 수 있다는 현재의 지식과 일치합니다.그러나 이러한 알고리즘에 대한 설명이 너무 빠르게 증가하여 단일 알고리즘으로는 가장 적합한 알고리즘을 자동으로 선택하여 실행할 수 없습니다.$만약{\displaystyle {\mathrm{}}^{}}$ 그렇다면, 2 o (${\displaystyle n^{}}$) ${\$$^{$$o$(n$)}$ 시간에 실행되는 알고리즘이 하나도 없음에도 ${\displaystyle {불구하고\mathrm{}}_{}}$ s 3$${\$displaystyle s_{3}}$는 0과 같습니다$$$.$^[3] 지수 시간 가설의 관련된 변형은 (각 길이마다 하나씩) 알고리즘 계열이 없다는 것을 가정하는 불균일 지수 시간 가설입니다.시간 2 ${\displaystyle o^{}}$ (${\displaystyle n^{}}$) ${\$^[4]$n)}}$에 3-SAT를 풀 수 있는 조언의 정신으로 입력의 h.

숫자 $s{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ s ${\displaystyle {4\mathrm{}}_{},}$ …$${\$displaystyle s_{3}, s_{4},\dots$}는 1에 의해 경계지어지는 단조로운 수열을 형성하기$$ 때문에, 그들은 한계로 수렴해야 합니다.

강력한 지수 시간 가설(SETH)은 ∞ = 1${\$displaystyle s_{\infty } = 1}이라는 추측입니다.

시사점

만족도

It is not possible for ${\displaystyle s_{k}}$ to equal ${\displaystyle s_{\infty }}$ for any finite ${\displaystyle k}$: as Impagliazzo, Paturi & Zane (2001) showed, there exists a constant ${\displaystyle \alpha }$ such that ${\displaystyle s_{k}\leq s_{\infty }(1-\alpha /k)}$.따라서 지수 시간 가설이 참이면 ${\displaystyle {sk}_{}}$ ${\$가 ${\displaystyle {sk}_{}}$+ ${\displaystyle 1_{}}$ ${\$과(와) 다른$$ $k{\displaystyle }$ ${\displaystyle k}$의 값이 무한히 많이 있어야 합니다$.$^[6]

이 영역에서 중요한 도구는 Impaglizo, Paturi & Zane(2001)의 희소화 보조정리인데, 이는 모든 변수 > 0${\$displaystyle $\varepsilon$>0}에 대해 $모든$ε ${\$displaystyle k} - CNF ${\displaystyle {공식}^{}}$은 ${\displaystyle O^{}}$2$$ε n) ${\displaystyle$ O(2$^{\$$varepsilon$n})} 더 $단순한$k${\$displaystyle k} - CNF 공식으로${\displaystyle }대체$될 수 있음을 보여줍니다.절의 개수가 선형인 상수 횟수입니다.희소화 보조정리는 주어진 공식에서 비어 있지 않은 공통 교집합을 갖는 큰 절들의 집합을 반복적으로 찾고 공식을 두 개의 더 간단한 공식으로 대체함으로써 증명됩니다. 하나는 이 절들 각각이 공통 교집합으로 대체되고 다른 하나는 각 절에서 교집합이 제거됩니다.희소화 보조정리를 적용한 다음 새로운 변수를 사용하여 절을 분할함으로써${\displaystyle {}^{}}$ (${\displaystyle 2^{}}$ε n) ${\displaystyle$ O($2^{\varepsilonn$})} 3-CNF 공식의 집합을 얻을 수 있으며, 각각은 선형 수의 변수를 가지고 있습니다.$원래$의 k ${\displaystyle k}-$CNF$$ 공식이 이 3-CNF 공식 중 적어도 하나가 만족스러운 경우에만 만족할 수 있도록 합니다.따라서 3-SAT를 하위 지수 시간에 해결할 수 있다면 이 감소를 사용하여 $k{\displaystyle }$ ${\displaystyle k}-$SAT를 하위 지수 시간에 해결할 수 있습니다.이와 동일하게 의 >0 {\$displaystyle k>0}$에 > 0 ${\displaystyle s_{k}>0$인 3 >0 {\$displaystyle s_{3$}>$0},$ 지수 시간 가설도 참이 됩니다.^[7][6]

$sk {\displaystyle$ s_{k} 시퀀스의 제한 $값$∞ {\$displaystyle$s_{\infty}}은$($는) 최대 s $CNF$ {\$displaystyle s_{\operatorname$CNF}},$여기$서 ${\displaystyle {\mathrm{CNF}}_{}}$ ${\displaystyle s_{\operatorname {CNF}}$는 절 길이 제한이 없는 연결 정규 형식식의 만족도를 ${\displaystyle {시간}^{}{O}^{}}$2$$δ n) ${\displaystyle O($2^{\delta})}에서 해결할 수 있도록 숫자$$δ ${\displaystyle$\delta} 중 최소값입니다.따라서 강력한 지수 시간 가설이 참이라면 모든 가능한 진리 할당에 대해 단순한 검색보다 훨씬 빠른 일반 CNF 만족도에 대한 알고리즘은 없을 것입니다.그러나 강력한 지수 시간 가설이 실패할 경우 s ${\displaystyle {\mathrm{CNF}}_{}}$ ${\$이(가) 1과 동일할$$ 수 있습니다.^[8]

기타 검색문제

지수 시간 가설은 복잡도 클래스 SNP의 다른 많은 문제에 일부 상수 $c{\displaystyle }$ ${\displaystyle c}$에 대해$$ 실행 시간이 ${\displaystyle {cn}^{}}$ ${\$보다 빠른 알고리즘이 없음을 의미합니다$.$이러한 문제에는 그래프 k-채색성, 해밀턴 사이클 찾기, 최대 클리크, 최대 독립 집합 및 $n{\displaystyle }$ ${\displaystyle$ n$}-$vertex$$ 그래프의 정점 커버가 포함됩니다.반대로, 이러한 문제 중 하나에 하위 지수 알고리즘이 있는 경우 지수 시간 가설이 거짓으로 나타날 수 있습니다.^[7][6]

다항 시간 내에 클릭 또는 로그 크기의 독립적인 집합을 찾을 수 있다면 지수 시간 가설은 거짓이 됩니다.따라서 이러한 작은 크기의 클라이크 또는 독립적인 집합을 찾는 것이 NP 완전하지 않을 가능성이 높더라도 지수 시간 가설은 이러한 문제가 비정형적임을 의미합니다.^[7][9]보다 일반적으로, 지수 시간 가설은 시간$)$ {\$displaystyle n^{o$(k$)}$에서 k $크기{\displaystyle }$ ${\displaystyle k}$의 클라이크 또는 독립적인 집합을 찾을 수 없음을$$^[10]의미합니다. 지수 시간 가설은 또한 k-SUM 문제를 해결할 수 없음을 의미합니다$($의 {\$displaystyle$ n$}$개의$$ 실수가 주어지면, $k개$의$${\$displaystyle$을 찾을 수 있음).${\displaystyle {0)}^{}}$에 추가되는 k$}개의$ 시간 ${\$ $n$$^{o(k)}}.$ 강력한 지수 시간 가설은 $시간{\displaystyle {}^{}}$ ${\displaystyle n^{}}$ k${\displaystyle {}^{}}$- ${\displaystyle o^{}}$(${\displaystyle {1)}^{}}$ ${\$보다 더 빠르게$k개$의 정점$$ 지배 집합을 찾을 수 없음을 의미합니다$.$^[8]

또한 지수 시간 가설은 토너먼트의 가중 피드백 아크 세트 문제가 실행 $시간$ O$$($2^{}$o ( ${\sqrt{\mathrm{OPT}}}^{}$) $n^{}$O ($1^{}$)$${\$textstyle$O ($2^{\sqrt {\operatorname {OPT}})}$ n$^{O(1)}}$인 매개 변수화된 알고리즘을 가지고 있지 않습니다$.$ 그러나 실행 시간 $O$(${\mathrm{}}^{}$ $O^{}$( ${\sqrt{\mathrm{OPT}}}^{}$) $n^{}$ ${}^{}{}^{}$( $1^{}$)${\tex$$tstyle O(2^{O({\sqrt {\operatorname {OPT}})}}n^{O$^[11]$1)}}.$

강력한 지수 시간 가설은 경계 트리 폭 그래프에서 여러 그래프 문제의 매개 변수화된 복잡성에 대한 엄격한 경계를 초래합니다.In particular, if the strong exponential time hypothesis is true, then the optimal time bound for finding independent sets on graphs of treewidth ${\displaystyle w}$ is ${\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}}$, the optimal time for the dominating set problem is ${\textstyle {\bigl ($$}3-o(1){\bigr )}^{w}n^{O(1)}}$, the optimum time for maximum cut is ${\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}}$, and the optimum time for ${\displaystyle k}$-coloring is ${\textstyle {\bigl (}k-o(1){\bigr )}^{w}n^{O(1)}}$.^[12] Equivalently,이러한 실행 시간에 대한 개선은 강력한 지수 시간 가설을 위조할 것입니다.^[13]지수 시간 가설은 또한 가장자리 클리크 덮개에 대한 고정 매개 변수 추적 가능 알고리즘이 매개 변수에 대해 두 배의 지수 종속성을 가져야 함을 의미합니다.^[14]

통신복잡도

통신 복잡도의 3자 집합 분리 문제에서, 일부 범위${\displaystyle }$[${\displaystyle 1,}$ ${\displaystyle m]}$ ${\displaystyle[1,$ m$]}$의 정수의 3개 부분 집합이 지정되고$$, 3개의 통신 당사자는 3개의 부분 집합 중 2개를 각각 알고 있습니다.목적은 공유 통신 채널에서 당사자들이 서로에게 적은 수의 비트를 전송함으로써 당사자들 중 한 명이 세 세트의 교차점이 비어 있는지 비어 있지 않은지 여부를 판단할 수 있도록 하는 것입니다.사소한 $m{\displaystyle }$ ${\displaystyle m}$ 비트$$ 통신 프로토콜은 세 당사자 중 한 명이 해당 당사자에게 알려진 두 집합의 교차점을 설명하는 비트 벡터를 전송하는 것이며, 그 후 남은 두 당사자 중 한 명이 교차점의 빈 공간을 결정할 수 있습니다.However, if there exists a protocol that solves the problem with ${\displaystyle o(m)}$ communication and ${\displaystyle 2^{o(m)}}$ computation, it could be transformed into an algorithm for solving ${\displaystyle k}$-SAT in time ${\displaystyle O(1.74^{n})}$ for any fixed constant ${\displaystyle k}$,강력한 지수 시간 가설을 위반하고 있습니다.따라서 강력한 지수 시간 가설은 3자 집합 분리에 대한 사소한 프로토콜이 최적이거나 더 나은 프로토콜이 기하급수적인 양의 계산을 필요로 한다는 것을 의미합니다.^[8]

구조복잡도

지수 시간 가설이 참이면 3-SAT는 다항식 시간 알고리즘을 갖지 않을 것이고, 따라서 P ≠ NP를 따를 것입니다. 더 강력한 것은 이 경우 3-SAT는 준다항식 시간 알고리즘도 가질 수 없었기 때문에 NP는 QP의 부분 집합이 될 수 없었습니다.그러나 지수 시간 가설이 실패하면 P 대 NP 문제에는 영향을 미치지 않습니다.패딩 인수는 < 1 {\$displaystyle$ c$<1}$에 대해 $가장$ 잘 알려진 실행 시간이 $O$${\mathrm{}}^{}$ n ${c^{}}^{}$ ${\$$textstyle O(2^{c})}$의 형태를 갖는 NP-완전 문제의 존재를 증명하며 3-SAT에 대해 가능한 가장 좋은 실행 시간이 이 형태일 경우,그러면 P는 NP와 같지 않지만(3-SAT가 NP-완전이고 이 시간 경계가 다항식이 아니기 때문에) 지수 시간 가설은 거짓이 됩니다.

매개 변수화된 복잡성 이론에서 지수 시간 가설은 최대 클리크에 대한 고정 매개 변수 추출 알고리듬이 존재하지 않음을 의미하기 때문에 W[1] ≠ FPT도 의미합니다.W[1] ≠ FPT가 지수 시간 가설을 의미합니까? 이 문제는 이 영역에서 중요한 미해결 문제는 W[1] ≠ FPT가 지수 시간 가설을 의미합니까?모든 $i$ ${\displaystyle i}$에 대하여$$$M{\displaystyle }$[${\displaystyle i}$] ⊆${\displaystyle }$W [ ${\displaystyle i}$] ⊆ M [ i + $1$ ] ${\displaystyle${\$mathsf$ {M$}[i]\subseteq${\$mathsf$ {W$}[i$]\$subseteq {\$mathsf {$M$i]; 예를 들어$,$$매개$ $k가 {\displaystyle$ k}인 ${\displaystyle$ n} - 정점 그래프에서$$크기 $k$ $로그$⁡ n ${\displaystyle$k\log n}의 정점 커버를 찾는 문제가 M[1]에 대해 완료되었습니다.지수 시간 가설은 M[1]이 FPT를 ≠한다는 문장과 같으며, i>$1 {\displaystyle$$$i>1}에 대한 M$i$⊆ W${\displaystyle [}$i] {\$displaystyle${\$mathsf {M}[i]\$ {\mathsf $}[$i]}도 열려 있습니다.

또한 강력한 지수 시간 가설의 변화 실패에서 복잡도 클래스의 분리에 이르기까지 다른 방향의 의미를 증명할 수도 있습니다.Williams(2010)가 보여주듯이, 만약 어떤 초대칭 성장 함수 $f{\displaystyle }$ ${\displaystyle f}$에 대해 시간$$ $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle n^{}}$ /${\displaystyle {}^{}}$f${\displaystyle }$(${\displaystyle n)}$ ${\displaystyle 2^{n}/f(n)}$에서 부울 회로 만족도를 해결하는 알고리즘$$ $A{\displaystyle }$ ${\displaystyle A}$가 존재한다면$,$ NEXPTIME은 P/poly의 부분 집합이 아닙니다.Williams는 알고리즘 $A{\displaystyle }$ ${\displaystyle A}$가 존재하고$$ P/poly에서 NEXPTIME을 시뮬레이션하는 회로 제품군도 존재한다면, 알고리즘 $A{\displaystyle }$ ${\displaystyle$ A$}$가 회로로 구성되어 더 적은 시간 내에 NEXPTIME 문제를 비결정적으로 시뮬레이션할 수 있으며$$ 시간 계층 정리를 위반할 수 있음을 보여줍니다.따라서 알고리즘 $A{\displaystyle }$ ${\displaystyle A}$의 존재는 회로 계열의 부재와 이 두 가지 복잡도 클래스의 분리를 증명합니다.^[15]

참고 항목

• 유사한 지수 갭이 공간 복잡도를 유지할 수 없음을 보여주는 Savitch의 정리

메모들

추가열람