1. 首頁
  2. 問答
  3. 每種語言都屬於P還是NP？

每種語言都屬於P還是NP？

2014-08-27 43 views
1

爲什麼我正在閱讀關於Michael Sipser計算理論的書，我有一個小問題：每種語言是屬於P還是NP？每種語言都屬於P還是NP？

來源

2014-08-27 little_monster

+0

有些語言「under」，就像NL類中的語言，還有其他的「over」，就像EXPSPACE類中的語言一樣。我認爲如果你繼續讀這本書會談論他們。 – 2014-08-27 09:58:35

+0

謝謝。我已經到達你談論的地點:) – 2014-08-28 10:50:06

+1

@FabioF。 NL不是P的子集嗎？ – templatetypedef 2014-09-08 20:12:50

回答

1

不是，並非P或NP中的所有語言。這裏有一些方法可以看到這一點：

  1. 有不可數許多語言，但只有在P與NP數多個語言。這意味着，特別是，如果您隨機選擇一種語言，並以概率1選擇一種語言，而不是P或NP。

  2. P和NP中的所有語言都是可判定的。任何不可判定的語言，如暫停問題，不能在NP中。

  3. nondeterministic time hierarchy theorem可用於顯示NEXP中有不在NP中的語言。

希望這有助於！

來源

2014-09-08 01:18:40 templatetypedef

相關問題

 相關問題