Revision as of 11:11, 3 April 2024 edit D.Lazard (talk \| contribs) Extended confirmed users 35,609 edits →Models of computation: clarification of "generally" Tag: Reverted ← Previous edit		Revision as of 11:07, 9 April 2024 edit undo 106.220.90.222 (talk) D.Lazard, stop spreading shit over Wiki pages) Undid revision 1217025972 by D.Lazard (talk) Tags: Undo Reverted Non-autoconfirmed user rapidly reverting edits Next edit →
Line 47: ==Models of computation== The evaluation of the complexity relies on the choice of a [[model of computation]], which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, itthis is generally{{According ~~implicitely~~to ~~assumed~~whom\|date=April 2024}} meant as being a [[multitape Turing machine]], since several more realistic models of computation, such as [[random-access machine]]s are asymptotically equivalent for most problems. It is only for very specific and difficult problems, such as [[integer multiplication]] in time <math>O(n\log n),</math> that the explicit definition of the model of computation is required for proofs. ===Deterministic models===

Computational complexity: Difference between revisions