2. The particular model of Turing machine, even if we restrict ourselves to
deterministic machines, affects the complexity. It is not clear what kind of
Turing machine is the best model of an actual computer, so an analysis
should not depend on any particular type of Turing machine.
3. We have found several languages that can be decided efficiently by a
nondeterministic Turing machine. For some, there are also reasonable
deterministic algorithms, but for others we know only inefficient, brute-force
methods. What is the implication of these examples?
Since the attempt to produce meaningful language hierarchies via timecomplexities with different growth rates appears to be unproductive, let us
ignore some factors that are less important, for example by removing some
uninteresting distinctions, such as that between DTIME(n k ) and DTIME(n k +1).
We can argue that the difference between, say, DTIME(n) and DTIME(n 2 ) is not
fundamental, since some of it depends on the specific model of Turing machine
we have (e.g., how many tapes). This leads us to consider the famous complexity
class
This class includes all languages that are accepted by some deterministic Turing
machine in polynomial time, without any regard to the degree of the polynomial.
As we have already seen, L REG and L CF are in P.
Since the distinction between deterministic and nondeterministic complexity
classes appears to be fundamental, we also introduce
Obviously
but what is not known is if this containment is proper. While it is generally
believed that there are some languages in NP that are not in P, no one has yet
found an example of this.
The interest in these complexity classes, particularly in the class P, comes
from an attempt to distinguish between realistic and unrealistic computations.