Revision as of 11:07, 9 April 2024 edit 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 ← Previous edit		Revision as of 12:14, 9 April 2024 edit undo Dedhert.Jr (talk \| contribs) Extended confirmed users 11,334 edits Undid revision 1218042027 by 106.220.90.222 (talk) Tag: Undo 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, ~~this~~it is generally~~{{According~~ toimplicitely ~~whom\|date=April 2024}} meant~~assumed 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