2
$\begingroup$

It is widely accepted that turing-complete systems are equivalent in terms of computability - i.e., whatever a turing-machine can do, can be emulated by automatas, the lambda calculus and other computing systems.

Not much is said about the efficiency of such systems. Intuitively speaking, it makes sense to think that some systems are less efficient than others. Is it possible to meaningfully categorizing such systems in term of efficiency?

$\endgroup$
  • $\begingroup$ I might be off base but I feel like efficiency is defined by the underlying rules of implementation - like hardware that defines what is fast or slow. At least, in part, since you can make decent generalizations like sticking to "classical computers" (non quantum) $\endgroup$ – Alan Wolfe Dec 5 '15 at 18:42
  • $\begingroup$ Usually, cost measures will be incompatible. $\endgroup$ – Raphael Dec 5 '15 at 20:56
2
$\begingroup$

If your model contains a notion of "step" (which is reasonable), and consequently defines the running time as the number of computational steps, then you can define the class $P$ for your model. If you think about polynomial time as efficient (which is what we normally do, see for example the question here), then you have a definition for what is efficiently solvable in your new model. You can now ask about the differences between the classes $P_M$ (set of languages decidable in polynomial time in the new model $M$), and the regular $P$ (which relates to Turing - machines).

Now, a reasonable definition for "the model $M$ is more efficient than $M'$" would be $P_{M'}\subsetneq P_M$.

Although $P$ has the advantage that it can be defined relative to any reasonable computational model, sometimes our notion of efficiency changes depending on the context.

For example, in quantum computation (for a formal definition of the model you can look up quantum circuits or quantum Turing machines) our notion of efficiency is captured by the class $BQP$ (since we involve error probabilities, it makes sense to allow our polynomial algorithm to be wrong with small probability). Same goes for the probabilistic Turing machine (Turing machines with the additional ability to toss coins). Our notion of "efficiently computable" with respect to probabilistic Turing machines is captured by the class $BPP$.

The question whether these models are "more efficient" than the classical Turing machine, translates to whether $P\subsetneq BQP$, and whether $P\subsetneq BPP$.

Since we know factoring integers is in $BQP$ (Shor's algorithm), and we suspect that it is not in $P$, we suspect that indeed $P\subsetneq BQP$, meaning that quantum computers can decide more problems efficiently (although it has the same computational power as the classical Turing-machine).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.