1
爲什麼我正在閱讀關於Michael Sipser計算理論的書，我有一個小問題：每種語言是屬於P還是NP？每種語言都屬於P還是NP？
A
回答
1
不是，並非P或NP中的所有語言。這裏有一些方法可以看到這一點：
有不可數許多語言，但只有在P與NP數多個語言。這意味着，特別是，如果您隨機選擇一種語言，並以概率1選擇一種語言，而不是P或NP。
P和NP中的所有語言都是可判定的。任何不可判定的語言，如暫停問題，不能在NP中。
nondeterministic time hierarchy theorem可用於顯示NEXP中有不在NP中的語言。
希望這有助於！
相關問題
- 1. Groovy和Groovy ++是兩種語言還是一種語言？
- 2. 哪種標記語言？降價還是？
- 3. AJAX是一種獨立於Javascript的語言，還是JavaScript框架？
- 4. Ruby是一種腳本語言還是一種解釋型語言？
- 5. Python是語言還是腳本語言？
- 6. 如果P = NP，爲什麼P = NP = NP-Complete？
- 7. PHP是一種Web技術還是一種腳本語言？
- 8. 每種語言的Vim-ab
- 9. SOLR索引每種語言/多種語言的SQL數據
- 10. 每種編程語言都有單獨的Subversion分支？
- 11. 是mysql查詢（INSERT，SELECT）屬於哪種語言？
- 12. 如果P = NP，是否存在NP中間體？
- 13. php是編譯語言還是解釋語言？
- 14. Hadoop Map/Reduce程序使用哪種語言？ Java還是PHP？
- 15. Codeigniter不同的DB爲每種語言
- 16. 爲每種語言設置DIR =「LTR」
- 17. Sitecore CMS - 每種語言的域名
- 18. Plone i18n - 每種語言需要多少
- 19. 是（a^p）（b^q）常規語言
- 20. ETL是解釋還是編譯語言
- 21. 是基於OS，語言環境還是其他的File.separatorChar？
- 22. 對於每種語言的另一個固定鏈接（Wordpress + qTranslate）
- 23. 兩種語言
- 24. 幾種語言
- 25. 任何人都認識到這種語法或編程語言？
- 26. 彙編語言move.l p， - （A3）
- 27. 學習一種新的編程語言取決於現有的熟悉語言是否是一種壞習慣？
- 28. 每種主要語言和平臺的使用率是多少？
- 29. 如何L = {wxw^R | w，x屬於{a，b}^+}是一種常規語言
- 30. 如果P！= NP，P是否比非P問題多，反之亦然？
有些語言「under」，就像NL類中的語言，還有其他的「over」，就像EXPSPACE類中的語言一樣。我認爲如果你繼續讀這本書會談論他們。 – 2014-08-27 09:58:35
謝謝。我已經到達你談論的地點:) – 2014-08-28 10:50:06
@FabioF。 NL不是P的子集嗎？ – templatetypedef 2014-09-08 20:12:50