Time hierarchy theorem: Difference between revisions

Revision as of 22:05, 27 December 2005

Revision as of 09:27, 26 February 2006

Line 66:

* [[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.

* {{Bookcite referencebook|Authorauthor = [[Michael Sipser]] | Yearyear = 1997 | Titletitle = Introduction to the Theory of Computation | Publisherpublisher = PWS Publishing | IDid = ISBN 0-534-94728-X}} Pages 310–313 of section 9.1: Hierarchy theorems.

* {{Bookcite referencebook|Authorauthor = [[Christos Papadimitriou]] | Yearyear = 1993 | Titletitle = Computational Complexity | Publisherpublisher = Addison Wesley | Editionedition = 1st edition | IDid = ISBN 0201530821}} Section 7.2: The Hierarchy Theorem, pp.143–146.

[[Category:Computational complexity theory]][[Category:Mathematical theorems]]