1
P與複雜性理論中的P完全相同嗎？ 我需要知道這兩個類是否相同。因爲我有一個Karp減少任何兩個，但無法在互聯網上找到它。P與P-Complete相同嗎？
A
回答
2
P中的任何問題可以多項式時間減少（二者許多酮和 圖靈）至幾乎任何其他問題在P.
的唯一原因說「幾乎」是因爲有一個問題（其中的補充）和其他問題可能很多 - 一個減少到 （儘管它們可以被Turing簡化爲）：接受 所有事物（以及拒絕所有事物的問題）的問題。
來源：Wikipedia
相關問題
- 1. p元素的長度與其中的文字相同嗎？
- 2. 已批量完成與啓用/ p LNK相同的任務嗎？
- 3. 是480x800與800x480相同嗎？
- 4. SQL與Join相同嗎？
- 5. '<？='與'echo'相同嗎？
- 6. Lua（Luvit）與Mongrel2相同嗎？
- 7. LWP與libwww-perl相同嗎？
- 8. Comparator.compareBoolean（）與Comparator.compare（）相同嗎？
- 9. dp與dip相同嗎？
- 10. SOAPpy與SOAPy相同嗎？
- 11. DbContext與DataContext相同嗎？
- 12. com.sun.org.apache與org.apache包相同嗎？
- 13. Oracle MySQL與MySQL相同嗎？
- 14. viewInstance.undelegateEvents（）與$（this.el）.unbind（）相同嗎？
- 15. random.random（）與random.uniform（）相同嗎？
- 16. ModelViewProjection與WorldViewProjection相同嗎？
- 17. $ PROGRAM_NAME與$ ruby相同嗎？
- 18. CTRL + M與Enter相同嗎？
- 19. JSON與GSON相同嗎？
- 20. URI與相對URL相同嗎？
- 21. 爲什麼* p ++與* p + = 1不同？
- 22. Request.Url.Host與Request.Headers [「host」]完全相同嗎？
- 23. Python模數與餘數相同嗎？
- 24. NoSQL中的元組與RDBMS相同嗎？
- 25. 是！$節日與$節日==相同嗎？
- 26. PHP for Windows與Linux，Mac等相同嗎？
- 27. Chrome上的閃存與Firefox相同嗎？
- 28. c3p0 maxIdleTime與mysql的wait_timeout相同嗎？
- 29. 指針的memcpy與賦值相同嗎？
- 30. DelegateCommand與「附加行爲」相同嗎？
通常情況下，談論P-完整性，減少超過多項式時間還原性較弱的形式在使用你所列出的原因。通常，使用類似logpace或AC^0還原性的東西。 – 2011-12-19 19:31:47