在計算複雜性理論中，複雜性類NEXPTIME（有時稱為NEXP）是一組決策問題，可以通過使用時間2n的非確定性圖靈機來解決。
基本介紹
- 外文名：NEXPTIME
- 別名：NEXP
介紹,替代特徵,完整的NEXPTIME,
介紹
在計算複雜理論內，複雜度類NEXPTIME（有時叫做NEXP）是一個決定性問題的集合，包含可以使用非確定型圖靈機，使用O(2)(這裡的p(n)是某個多項式）的實踐可以解決的問題。另外這裡不限制空間的使用。
一個很重要的NEXPTIME-完全問題集合與簡潔電路(succinct circuit)有關。簡潔電路是能以指數速率縮減的空間形容圖的一個機器。這個機器接收兩個頂點的號碼為輸入，輸出這兩個頂點是否有邊相連。如果有個問題，使用一般的圖表示法，像是連線矩陣，去解決時是個NP-完全問題，那么使用簡潔電路的表示來解決這個問題是NEXPTIME-完全，因為輸入的大小跟前者相比是成指數速率縮小。舉個簡單的例子，使用簡潔電路的表示法找一張圖的哈密頓圖是NEXPTIME-完全。
替代特徵
NEXPTIME經常出現在互動式證明系統的背景下，其中有兩個主要特徵。第一個是MIP證明系統，其中我們有兩個全能的證明器，它們與隨機多項式時間驗證器（但彼此不相關）進行通信。如果字元串是語言，他們必須能夠以高機率說服驗證者。如果字元串不在語言中，則他們必須無法協作地欺騙驗證者接受字元串，除非機率很低。 MIP證明系統可以解決NEXPTIME中的每個問題這一事實令人印象深刻，當我們考慮到當只有一個證明者存在時，我們只能識別所有PSPACE;驗證者“交叉檢查”兩個證明者的能力賦予它巨大的力量。有關詳細信息，請參閱互動式校樣系統#MIP。
另一種表征NEXPTIME的互動式證明系統是一類機率可檢驗證明。回想一下，NP可以被視為一類問題，其中一個全能的證明者給出了一個聲稱字元串在語言中的證明，並且確定性多項式時間機器驗證它是一個有效的證明。我們對此設定進行了兩處更改：
1、添加隨機性，翻轉硬幣的能力，到驗證機。
2、不是簡單地將聲稱的證據提供給磁帶上的驗證者，而是隨機訪問證明。驗證者可以指定證明字元串的索引並接收相應的位。由於驗證者可以寫出多項式長度的索引，因此它可以潛在地索引到指數長的證明字元串。
這兩個擴展共同極大地擴展了證明系統的功能，使其能夠識別NEXPTIME中的所有語言。該類稱為PCP （poly，poly）。此外，在該表征中，驗證器可以被限制為僅讀取恆定數量的比特，即NEXPTIME = PCP （poly，1）。有關詳細信息，請參閱機率可檢查證明。
完整的NEXPTIME
如果它在NEXPTIME中，則決策問題是NEXPTIME-complete，並且NEXPTIME中的每個問題都具有多項式時間多次減少。換句話說，存在一種多項式時間算法，該算法將一個實例轉換為具有相同答案的另一個實例。 NEXPTIME完成的問題可能被認為是NEXPTIME中最難的問題。我們知道NEXPTIME完全問題不在NP中;已經證明，這些問題不能通過時間層次定理在多項式時間內得到驗證。
一組重要的NEXPTIME完整問題涉及簡潔的電路。簡潔的電路是用於以指數級較小的空間描述圖形的簡單機器。它們接受兩個頂點數作為輸入和輸出它們之間是否存在邊緣.如果在自然表示中解決圖形上的問題（例如鄰接矩陣）是NP完全的，那么在簡潔的電路表示上解決相同的問題是NEXPTIME完成的,因為輸入指數小（在某些溫和的條件下,通過“投影”實現NP完全性降低。作為一個簡單的例子，為這樣編碼的圖找到哈密頓路徑是NEXPTIME完成的。
