Complexity Theory, Exponential Time
Exponential Time
A language belongs to the class e (exponential),
if it is recognized by a tm within e(|w|) steps,
where |w| is the length of the input word, and e(n) is a fixed exponential function, specific to that tm,
that does not depend on w.
This is similar to the definition of a p language, where the execution time is bounded by a polynomial.
An exponential function e(n) is of the form p(kq(n)),
where p and q are polynomials, and k is an integer greater than 1.
This somewhat broader definition of exponential permits reduction from one language to another.
If l1 reduces to l2 in polynomial time,
and l1 is an e language, then so is l2.
One can also talk about ne languages,
which are recognized by nondeterministic tms in exponential time,
but this doesn't seem to have any practical applications.
Hey, if a nondeterministic computer requires exponential time to solve the problem,
it may as well be undecidable.
e ≥ np
Let m1 be an ntm that recognizes l1 in polynomial time.
In other words, l1 is an np language.
Recall that a deterministic tm m2 can simulate m1, with an exponential slowdown.
In this case we can run a depth first search, instead of a breadth first search,
because we know m1 will not take more than p(|w|) steps.
This is a bit faster, and a bit easier to understand at an intuitive level,
but any way you slice it, it's an exponential slowdown.
If m1 has at most k choices for a state transition,
m2, with its stack on a separate track, is bounded by kp(|w|).
Pulling m2 back to a single-track tm might introduce a quadratic slowdown, but it's still an exponential function, as described above.
Every np language lies in e, and we can write the following.
e ≥ np ≥ p