Content deleted Content added
m Robot-assisted disambiguation: Complexity classes P and NP |
→References: no inline refs, change to "Sources" and add {[reflist}} in case someone wishes to add inline refs |
||
Line 72:
However, the time hierarchy theorems provide no means to relate deterministic and non-deterministic complexity, or time and space complexity, so they cast no light on the great unsolved questions of [[complexity theory]]: whether [[P=NP problem|P and NP]], NP and [[PSPACE]], PSPACE and EXPTIME, or EXPTIME and NEXPTIME are equal or not.
==
{{reflist}}
== Sources==
* [[Stephen Cook]] (1972). [http://portal.acm.org/citation.cfm?id=804913 A hierarchy for nondeterministic time complexity]. ''Proceedings of the fourth annual ACM symposium on Theory of computing'', pp.187–192.
| |||