Suggest edit — Time Complexity

Title

Name

Note

---
title: "Time Complexity"
type: concept
related: [Turing Machinea, Time Complexity, Non Deterministic Computation, Regular Language, Amortized Analysis]
source: https://www.jemoka.com/posts/kbhtime_complexity/
confidence: high
status: active
---

Time complexity $t(n): \mathbb{N} \to \mathbb{N}$, and:
\begin{equation} \text{TIME}\qty(t(n)) = \qty {\text{languages } L \mid\ \exists \text{TM that decides $L$ in $O(t(n))$ steps} } \end{equation}
notice! the Big-oh is backed into the definition. And we write:
\begin{equation} P = \bigcup_{c \in \mathbb{N}} \text{TIME}\qty(n^{c}) \end{equation}
we call this &ldquo;efficient&rdquo; vs. &ldquo;feasible&rdquo;.
\begin{equation} EXP = \bigcup_{c \in \mathbb{N}} \text{TIME}\qty(2^{n^{c}}) \end{equation}
and adding in non-determinism, we have:
\begin{equation} \text{NTIME}\qty(t(n)) = \qty {L : \exists\ \text{NTM that decides L in O(t(n)) steps}} \end{equation}
and so:
\begin{equation} NP = \bigcup_{c \in \mathbb{N}} \text{NTIME}\qty(n^{c}) \end{equation}
turing machine Time Complexity We measure a turing machine&rsquo;s time complexity via number of steps it takes for a turing machine to halt.
Let $M$ be a turing machine that halts on all inputs; we will only consider for now decidable languages. We define:
the running time or Time Complexity of the machine $M$ is a function $T : \mathbb{N} \to \mathbb{N}$, such that $T(n)$ is the maximum number of steps taken by $M$ over all inputs of length $n$ (the &ldquo;worst case complexity&rdquo;).
Time-Bounded Complexity Let us define:
\begin{equation} \text{TIME}\qty(t(n)) = \qty {L&rsquo; \mid \text{there&rsquo;s a TM $M$ with time complexity $O(t(n))$ so that $L&rsquo; = L(M)$}} \end{equation}
that is, $\text{TIME}(T(n))$ a set of languages decided by some TM with $O(t(n))$ running time.
Polynomial Time \begin{equation} P = \bigcup_{k \in N} \text{TIME}\qty(n^{k}) \end{equation}
&ldquo;efficient&rdquo;; and &ldquo;robust&rdquo;: that is, multi-tape TM theorem (number of tapes, etc.) and time hierarchy theorem
Extended Church-Turing Thesis see Extended Church-Turing Thesis
one-tape TM cannot decide some language $A$ in less than $O(n \log n)$ time For any
\begin{equation} f(n) = O\qty( \frac{n \log n}{\alpha \qty (n)}) \end{equation}
where $\alpha(n)$ is unbounded, we have that $TIME(f(n))$ contains only regular languages.
two tapes could be more powerful than one tape &hellip;because you can do things in parallel (i.e. different models of computation can yield different run times, even if they are both computable function)
in fact, something like $B = \qty { ww \mid w \in \qty {0,1}^{*}}$ has a quadratic gap
multi-tape TM theorem Let $t: \mathbb{N} \to \mathbb{N}$, which satisfies $t(n) \geq n$, for all $n$. Then, every $t(n)$ time multi-tape TM has an equivalent $O\qty (t(n)^{2})$ time one-tape TM.
Its transition function is:
\begin{equation} \delta : Q \times \Gamma^{k} \to Q \times \Gamma^{k-1} \times \qty {L, R, S}^{k} \end{equation}
&hellip;.because you can just append the tapes in the style of multi-tape simulation by one tape and then just move across all of $n$ each time to increment the next tape.
correlary: suppose language $A$ can be decided by a multi-tape Turing Machine in $p(n)$ steps for some polynomial $p$, then $A$ can be decided by a one-tape TM in $q(n)$ steps, by some polynomial $q$ (because we just squared in the example above).
efficient universal Turing Machine there is a one-tape Turing Machine $U$ which takes as input&hellip;.
the code of an arbitrary Turing Machine $M$ an input string $w$ and a string of $t$ 1s which represents the runtime where $t &gt; |w|$ such that $U\qty (M,w, 1^{t})$ halts in $O\qty (|M|^{2} t^{2})$ steps and $U$ accepts $\qty (M, w, 1^{t}) \Leftrightarrow M$ accepts $w$ in $t$ steps.
That is&hellip;. the universal Turning machine will not run forever; its a clock that goes to a certain amount of steps and gives up.
The idea to make this is to make a multi-tape TM $U&rsquo;$ that does the above, and run the multi-tape reduction.
time hierarchy theorem &ldquo;if you get more time to compute then you can solve strictly more problems&rdquo;
254:
If $t(n), T(n)$ are such that $t(n) \geq n$ where $T(n) = \omega \qty(t(n) \log\qty(t(n)))$, then $\text{TIME}\qty(t(n)) \subset \text{TIME} \qty(T(n))$.
154:
For all reasonable (&ldquo;constructible&rdquo;) $f,g: \mathbb{N} \to \mathbb{N}$ where for all $n$, $g(n) &gt; n^{2} f(n)^{2}$, then $\text{TIME}(f(n)) \subset \text{TIME}(g(n))$ strictly contain.
proof idea: Diagonalization Arguments with a clock; make a Turing machine $N$ on input $M$; simulate $M$ on input $M$ for $f(|M|)$ steps then flip the answer.
Proof:
let us define some machine $N(M)$ which computes in $t = f(|M|)$. Run $U\qty (M, M, 1^{t})$, and output the opposite answer.
Assume for contradiction $L(N)$ has time complexity $f(n)$. By assumption, $N(N)$ runs in $f(|N|)$ time and outputs the opposite answer as $U\qty (N, N, 1^{f\qty (|N|)})$. This is contradiction because $N(N)$ outputting true means $U(N, N)$ outputs false, etc. Tish is a contradiction.
This means that $L(N)$ does not have time complexity $f(n)$.
Recall however $U\qty (N, N, 1^{f\qty (|N|)})$ halts in $O\qty (|M|^{2} t^{2})$ steps, so let&rsquo;s set $g(|M|) &gt; |M|^{2} f(|M|)^{2}$ for all $M$.
(This also holds for multiple Turing Machines).
correlary
\begin{equation} \text{TIME}\qty(n) \subset \text{TIME}\qty(n^{2}) \subset \dots \end{equation}
there are an infinite hierarchy of increasingly time-consuming problems
example same number \begin{equation} A = \qty {0^{k} 1^{k} \mid k \geq 0} \end{equation}
for a turing machine on $A$, on input of length $n$, we&hellip;.
first pass: scan the tape and reject if the string is not of the form $0^{i}1^{j}$ repeat if both $0$s and $1$s are an the tape scan across the tape, crossing off a single $0$ and a single $1$ if $0$ remain after all $1$ crossed off, then reject. otherwise, accept This has complexity of&hellip;
single scan: $O(n)$ crossing off left right: $O\qty (n^{2})$ verifying: $O(n)$ actually, though, we can do this in $O(n \log n)$ if $w$ is not in the right shape $0^{*}1^{*}$, reject repeat until all bits of $w$ are crossed out if parity (odd/evenness) of $0$ is not parity of $1$, reject cross out every other $0$, cross out ever other $1$ if all bits crossed out, accept There will be $\log n$ crossings-out at most (since each divides by $2$), and each of such crossings-out, will check linearly.