一千萬個為什麽

搜索

“自然的”可判定的問題已知不在NP中。

每當我教NP-Completeness時,學生都會問“有什麽問題已知不屬於NP?”

你會怎麽回答?作為一個例子,我通常給他們一個不可判定的問題,但這通常不會很好:(a)如果我給他們停止問題他們認為這是一些愚蠢的角落情況,(b)如果我給他們Diophantine方程他們不明白為什麽它不在NP中(你可以在聚合時間檢查解決方案......只需插入它們!我很難解除它們的這種方法。)

我想給他們一些類似QBF的例子,但沒有經過證明的分離。

建議?

最佳答案

一種可能性是EXPSPACE-complete的問題。 NP在PSPACE中非常簡單,PSPACE嚴格包含在EXPSPACE中。 EXPSPACE-complete的一個問題是決定允許取冪的正則表達式是否全部$ \西格瑪^ * $

轉載註明原文: “自然的”可判定的問題已知不在NP中。