1
P与复杂性理论中的P完全相同吗？ 我需要知道这两个类是否相同。因为我有一个Karp减少任何两个，但无法在互联网上找到它。P与P-Complete相同吗？
A
回答
2
P中的任何问题可以多项式时间减少（二者许多酮和 图灵）至几乎任何其他问题在P.
的唯一原因说“几乎”是因为有一个问题（其中的补充）和其他问题可能很多 - 一个减少到 （尽管它们可以被Turing简化为）：接受 所有事物（以及拒绝所有事物的问题）的问题。
来源：Wikipedia
相关问题
- 1. 已批量完成与启用/ p LNK相同的任务吗？
- 2. DbContext与DataContext相同吗？
- 3. LWP与libwww-perl相同吗？
- 4. viewInstance.undelegateEvents（）与$（this.el）.unbind（）相同吗？
- 5. '<？='与'echo'相同吗？
- 6. 是480x800与800x480相同吗？
- 7. Comparator.compareBoolean（）与Comparator.compare（）相同吗？
- 8. dp与dip相同吗？
- 9. CTRL + M与Enter相同吗？
- 10. $ PROGRAM_NAME与$ ruby相同吗？
- 11. Lua（Luvit）与Mongrel2相同吗？
- 12. SOAPpy与SOAPy相同吗？
- 13. com.sun.org.apache与org.apache包相同吗？
- 14. random.random（）与random.uniform（）相同吗？
- 15. URI与相对URL相同吗？
- 16. SQL未知与NULL相同吗？
- 17. ReaderWriterLockSlim.EnterUpgradeableReadLock（）与Monitor.Enter（）基本相同吗？
- 18. SeDebugPrivilege（）api的功能与System.Diagnostics.Process.EnterDebugMode相同吗？
- 19. Ruby的“绑定”与Scope Chain相同吗？
- 20. $（'selector'，element）与element.find（'selector'）相同吗？
- 21. ASP Session变量：与IsEmpty相同吗？
- 22. DelegateCommand与“附加行为”相同吗？
- 23. Android Webview与Chrome浏览器相同吗？
- 24. ||运算符与=运算符相同吗？
- 25. php urlencode与java urlencode相同吗？
- 26. EventAggregator.PublishOnUIThread（aMessage）与EventAggregator.Publish（aMessage，Execute.OnUIThread）相同吗？
- 27. dmPaperSize = DMPAPER_USER与dmPaperSize = 0相同吗？
- 28. ReferenceEquals（null，obj）与null == obj相同吗？
- 29. ConcurrentDictionary.Acount> 0与ConcurrentDictionary.Any（）相同吗？
- 30. 捆绑与捆绑安装相同吗？
通常情况下，谈论P-完整性，减少超过多项式时间还原性较弱的形式在使用你所列出的原因。通常，使用类似logpace或AC^0还原性的东西。 – 2011-12-19 19:31:47