一千萬個為什麽

搜索

我有一個問題,在NEXP $ ^ {\ text {NP}} $中,也可以通過交替TM使用指數時間和只有一個交替(從存在狀態開始)來解決。

NEXP $ ^ {\ text {NP}} $有什麽已知的嗎?它等於NEXP還是其他類?除了通用問題之外是否存在完整的問題(給定NEXP $ ^ {\ text {NP}} $機器和一個單詞,它是否接受?)。

最佳答案

一個自然的$ \ text {NEXP} ^ {\ text {NP}} $ - 完全問題是用$ \ exists ^ * \ forall ^ * \ exists ^ * $ - 量詞前綴決定Presburger算術的句子(如圖所示< a href =“http://arxiv.org/abs/1401.5266”>這裏)。已經在這裏研究了與數據庫理論相關的更完整的問題。

轉載註明原文: 復雜度類NEXP $ ^ \ text {NP} $

猜你喜歡