Revision as of 07:17, 3 April 2024 edit Electro (talk \| contribs) 35 edits m Mark unsourced statement that the default model is a multitape Turing machine ← Previous edit		Revision as of 11:11, 3 April 2024 edit undo D.Lazard (talk \| contribs) Extended confirmed users 35,609 edits →Models of computation: clarification of "generally" Tag: Reverted 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