Editing Computational complexity theory (section)

===Other machine models===
Many machine models different from the standard [[Turing machine equivalents#Multi-tape Turing machines|multi-tape Turing machines]] have been proposed in the literature, for example [[random-access machine]]s. Perhaps surprisingly, each of these models can be converted to another without providing any extra computational power. The time and memory consumption of these alternate models may vary.<ref>See {{harvnb|Arora|Barak|2009|loc=Chapter 1: The computational model and why it doesn't matter}}</ref> What all these models have in common is that the machines operate [[deterministic algorithm|deterministically]].

However, some computational problems are easier to analyze in terms of more unusual resources. For example, a non-deterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The non-deterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that [[non-deterministic time]] is a very important resource in analyzing computational problems.