Revision as of 15:53, 3 October 2005 edit Timwi (talk \| contribs) Administrators 32,166 edits →Statement: little note, suggested on talk page ← Previous edit		Revision as of 22:32, 19 November 2005 edit undo Dcoetzee (talk \| contribs) 37,529 edits Add references Next edit →
Line 62: 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 [[Complexity classes P and NP\|P and NP]], NP and [[PSPACE]], PSPACE and EXPTIME, or EXPTIME and NEXPTIME are equal or not. == References == * {{Book reference\|Author = [[Michael Sipser]] \| Year = 1997 \| Title = Introduction to the Theory of Computation \| Publisher = PWS Publishing \| ID = ISBN 0-534-94728-X}} Pages 310–313 of section 9.1: Hierarchy theorems. * {{Book reference\|Author = [[Christos Papadimitriou]] \| Year = 1993 \| Title = Computational Complexity \| Publisher = Addison Wesley \| Edition = 1st edition \| ID = ISBN 0201530821}} Section 7.2: The Hierarchy Theorem, pp.143–146. [[Category:Computational complexity theory]][[Category:Theorems]]

Time hierarchy theorem: Difference between revisions