Editing Computational complexity (section)

==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, it is generally implicitely 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===
A [[deterministic model]] of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were [[μ-recursive function|recursive function]]s, [[lambda calculus]], and [[Turing machine]]s. The model of [[random-access machine]]s (also called RAM-machines) is also widely used, as a closer counterpart to real [[computer]]s.

When the model of computation is not specified, it is generally assumed to be a [[multitape Turing machine]]. For most algorithms, the time complexity is the same on multitape Turing machines as on RAM-machines, although some care may be needed in how data is stored in memory to get this equivalence.

===Non-deterministic computation===
In a [[non-deterministic algorithm|non-deterministic model of computation]], such as [[non-deterministic Turing machine]]s, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to [[quantum computing]] via superposed [[entangled state]]s in running specific [[quantum algorithms]], like e.g. [[Shor's algorithm|Shor's factorization]] of yet only small integers ({{as of|2018|03|lc=yes}}: 21 = 3 × 7).

Even when such a computation model is not realistic yet, it has theoretical importance, mostly related to the [[P = NP]] problem, which questions the identity of the complexity classes formed by taking "polynomial time" and "non-deterministic polynomial time" as least upper bounds. Simulating an NP-algorithm on a deterministic computer usually takes "exponential time". A problem is in the complexity class [[NP (complexity)|NP]], if it may be solved in [[polynomial time]] on a non-deterministic machine. A problem is [[NP-complete]] if, roughly speaking, it is in NP and is not easier than any other NP problem. Many [[combinatorics|combinatorial]] problems, such as the [[Knapsack problem]], the [[travelling salesman problem]], and the [[Boolean satisfiability problem]] are NP-complete. For all these problems, the best known algorithm has exponential complexity. If any one of these problems could be solved in polynomial time on a deterministic machine, then all NP problems could also be solved in polynomial time, and one would have P = NP. {{As of|2017}} it is generally conjectured that {{nowrap|P ≠ NP,}} with the practical implication that the worst cases of NP problems are intrinsically difficult to solve, i.e., take longer than any reasonable time span (decades!) for interesting lengths of input.

===Parallel and distributed computation===
{{main|Parallel computing|Distributed computing}}
Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a [[computer network|network]] and is therefore much slower.

The time needed for a computation on {{mvar|N}} processors is at least the quotient by {{mvar|N}} of the time needed by a single processor. In fact this theoretically optimal bound can never be reached, because some subtasks cannot be parallelized, and some processors may have to wait a result from another processor.

The main complexity problem is thus to design algorithms such that the product of the computation time by the number of processors is as close as possible to the time needed for the same computation on a single processor.

===Quantum computing===
A [[quantum computer]] is a computer whose model of computation is based on [[quantum mechanics]]. The [[Church–Turing thesis (complexity theory)|Church–Turing thesis]] applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower [[time complexity]] using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer.

[[Quantum complexity theory]] has been developed to study the [[complexity class]]es of problems solved using quantum computers. It is used in [[post-quantum cryptography]], which consists of designing [[cryptographic protocol]]s that are resistant to attacks by quantum computers.