指數時間假設

在計算複雜性理論中，指數時間假設是一個未經證實的計算硬度假設，它是由Impagliazzo＆Paturi（1999）提出的。它指出， 3-CNF布爾公式的滿意度無法在次指數時間內解決， 。更確切地說，假設的通常形式斷言了一個數字的存在使所有正確解決此問題的算法至少需要時間 。指數時間假設（如果為true）將暗示p≠np ，但這是一個更強有力的陳述。這意味著許多計算問題在復雜性上是等效的，因為如果其中一個具有次指數時間算法，那麼它們都這樣做，並且這些問題的許多已知算法具有最佳或近乎最佳的時間複雜性。

定義

這 -問題問題是布爾滿意度問題的一種版本，其中該問題的輸入是以結合性正常形式（即變量及其否定）的布爾表達式，最多最多可以每個條款變量。目的是通過將布爾值分配給其變量來確定是否可以使此表達式成為真實。 2-SAT具有線性時間算法，但所有已知算法的較大算法花費指數時間，並取決於指數函數的基礎 。例如， Walksat概率算法可以解決 -平均時間

在哪裡是給定的變量數量 -sat實例。對於每個整數 ，定義是最小的數字 -可以在時間上解決 。如果一系列越來越更好的算法在其時間範圍內的指數增長較小，則可能不存在該最低限度。在這種情況下，定義成為實數的最低數字為此 -可以在時間上解決 。因為較大的問題不能容易，這些數字被排序為 ，由於走路，他們最多是指數時間假設是猜想它們都是非零的，或同等的，其中最小的是 ，非零。

一些來源將指數時間假設定義為稍弱，即無法及時解決3-SAT 。如果存在算法以求解3個SAT ，然後將等於零。但是，這與當前的知識一致，即可能有一系列3個SAT算法，每個算法都與運行時間對於數字序列趨向零，但是如果這些算法的描述如此之快，以至於單個算法無法自動選擇並運行最合適的算法。如果是這樣，那就即使不會及時運行單個算法，也會等於零 。指數時間假設的相關變體是不均勻的指數時間假設，它認為沒有算法家族（以建議的精神，每個輸入的長度一個）可以在時間上解決3-SAT。 。

因為數字形成一個單調序列，在上面的一個界限上，它們必須收斂到極限

強烈的指數時間假設（SETH）是猜想 。

含義

令人滿意

不可能等於對於任何有限的 ：正如Impagliazzo一樣，Paturi＆Zane（2001）表明，存在一個常數這樣 。因此，如果指數時間假設是正確的，則必須有無限的值為此不同於 。

該領域的一個重要工具是Impagliazzo，Paturi＆Zane（2001）的稀疏引理，這表明，對於每個 ，任何 -CNF公式可以用更簡單 -CNF公式，其中每個變量僅出現恆定次數，因此子句的數量是線性的。稀疏引理是通過反复找到在給定公式中具有非空的共同相交的大量子句，並用兩個更簡單的公式代替公式的，其中一個將這些條款替換為這些條款，其中一個將其替換為其共同的交叉點，另一個將其代替。從每個子句中刪除了相交。通過應用稀疏引理，然後使用新變量拆分條款，然後可以獲得一組 3-CNF公式，每個公式都有線性數量的變量，以便原始當且僅當這些3-CNF公式中的至少一個可滿足時， CNF公式是可滿足的。因此，如果可以在次指數時間內解決3個SAT，則可以使用此減少來解決 -在次指數時間內也要介紹。等效，如果任何 ，然後同樣，指數時間假設也是如此。

限制值數字順序最多等於 ，在哪裡是數字的最低因此，可以在沒有子句長度限制的情況下的結合性正常形式公式的滿意度來解決 。因此，如果強烈的指數時間假設是正確的，那麼一般CNF的滿意度就不會比所有可能的真實分配的蠻力搜索要快得多。但是，如果強大的指數時間假設失敗，仍然有可能等於一個。

其他搜索問題

指數時間假設意味著複雜性類SNP中的許多其他問題沒有算法的運行時間快對於一些常數 。這些問題包括圖k-可亮性，查找哈密頓週期，最大集團，最大獨立集和頂點覆蓋 -vertex圖。相反，如果這些問題中的任何一個具有亞指數算法，則指數時間假設可以證明是錯誤的。

如果可以在多項式時間中找到集團或獨立的對數大小，則指數時間假設將是錯誤的。因此，即使找到如此小的大小的集團或獨立集不太可能是np完整的，但指數時間假設意味著這些問題是非多項式的。更一般地，指數時間假設意味著找不到大小的集團或獨立集合及時 。指數時間假設也意味著無法解決K -Syum問題（給定實數，查找其中添加到零）的時間 。強烈的指數時間假設意味著無法找到 -vertex主導集比及時更快 。

指數時間假設也意味著錦標賽上的加權反饋弧設置問題與運行時間沒有參數化算法 。但是，它確實具有運行時間的參數化算法 。

強大的指數時間假設導致在有界樹寬圖上的幾個圖形問題的參數化複雜性上的緊密界限。特別是，如果強烈的指數時間假設是正確的，則最佳時間綁定用於在Treewidth上查找獨立集是 ，主導設置問題的最佳時間是 ，最大切割的最佳時間是 ，以及最佳時間 - 顏色是 。同等地，對這些運行時間的任何改進都將偽造強大的指數時間假設。指數時間假設還意味著任何用於邊緣集合覆蓋物的固定參數可處理算法都必須對參數具有雙重指數依賴性。

溝通複雜性

在溝通複雜性的三方集合不相交問題中，整數的三個子集在某些範圍內指定，三個交流方每個都知道這三個子集中的兩個。目的是讓各方在共享通信渠道上互相傳輸很少的位，以便當事方之一能夠確定三組的交匯處是空的還是非空的。一個瑣碎的 -bit通信協議將是針對三方之一，以傳輸描述該方已知的兩組相交的比特矢量，然後其餘兩個當事方中的任何一個都可以確定交叉路口的空虛。但是，如果存在解決問題的協議溝通和計算，它可以轉換為求解算法 -時間對於任何固定常數 ，違反了強烈的指數時間假設。因此，強烈的指數時間假設意味著三方集合的瑣碎協議是最佳的，或者任何更好的協議都需要指數級的計算量。

結構複雜性

如果指數時間假設是正確的，則3-SAT不會具有多項式時間算法，因此將遵循p≠np 。更強烈的是，在這種情況下，3-SAT甚至無法具有準多項式時間算法，因此NP不可能是QP的子集。但是，如果指數時間假設失敗，則對P與NP問題無關。填充論點證明了NP完整問題的存在，最著名的運行時間具有形式為了 ，如果3個SAT的最佳運行時間是這種形式，那麼P將與NP不等（因為3-SAT是NP完整的，並且此時間限制不是多項式），但是指數時間假設是錯誤的。

在參數化的複雜性理論中，因為指數時間假設意味著對於最大列表不存在固定參數算法，這也意味著w [1]≠fpt 。在該領域是否可以逆轉這一含義是一個重要的開放問題： w [1]≠fpt是否意味著指數時間假設？有一個稱為M層次結構的參數化複雜性類別的層次結構，它交織了W層體系結構，從某種意義上說， ，，，， ;例如，查找大小的頂點蓋的問題在 - 帶有參數的vertex圖對於M [1]是完整的。指數時間假設等同於m [1]≠fpt的陳述，以及是否的問題為了也開放。

還可以從強大的指數時間假設的變化到復雜性類別的分離的變化，從另一個方向上證明含義。如Williams（2010）所示，是否存在算法解決布爾電路時的滿意度對於某些超多生體增長的功能 ，那麼nexptime不是p/poly的子集。威廉姆斯表明，如果算法存在，並且還存在模擬Nexptime的一系列電路家族，也存在算法可以與電路組成，以在較小的時間內無確定地模擬Nexptime問題，從而違反了時間層次結構定理。因此，算法的存在證明了電路家族的不存在和這兩個複雜性類別的分離。

也可以看看