NEXPTIME

维基百科,自由的百科全书
跳转至: 导航搜索

計算複雜度理論內,複雜度類 NEXPTIME (有時叫做NEXP)是一個決定性問題的集合,包含可以使用非確定型圖靈機,使用O(2p(n))(這裡的p(n)是某個多項式)的時間可以解決的問題。另外這裡不限制空間的使用。

NTIME作定義

\mbox{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(2^{n^k})

一個很重要的NEXPTIME-完全問題集合與簡潔電路(succinct circuit)有關。簡潔電路是能以指數速率縮減的空間形容圖的一個機器。這個機器接收兩個頂點的號碼為輸入,輸出這兩個頂點是否有邊相連。如果有個問題,使用一般的圖表示法,像是連接矩陣,去解決時是個NP-完全問題,那麼使用簡潔電路的表示來解決這個問題是NEXPTIME-完全,因為輸入的大小跟前者相比是成指數速率縮小。[1]舉個簡單的例子,使用簡潔電路的表示法找一張圖的哈密頓圖NEXPTIME-完全。

如果P = NP,那麼NEXPTIME = EXPTIME;更精確的說,ENE,若且唯若存在一個稀疏語言,在NP並且不在P裡面。[2]


相關條目[编辑]

參考資料[编辑]

  1. ^ C. Papadimitriou. Computational Complexity Addison-Wesley, 1994. ISBN 0-201-53082-1. Section 20.1, pg.492.
  2. ^ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library