Time Complexity Flashcards
Definition 5.1 (Time Complexity)
Let M be a deterministic decider, i.e. a deterministic TM that halts on all inputs. We define the running time or time complexity of M as the function f : N → N, such that f(n) is the maximum number of steps or transitions that M uses on any input of length n. In that case, we say that “M runs in time f(n)” or “M is an f(n) time Turing machine”.
Definition 5.2 (Asymptotic Upper Bound)
Let f, g be functions of form f, g : N → R≥0. We say that
f(n) = O(g(n))
if there exists a real number c > 0 and an integer n0 > 0 such that for every integer n ≥ n0, we have
f(n) ≤ c g(n).
In this case we say that g(n) is an (asymptotic) upper bound for f(n).
Definition 5.3 (Exponential and Polynomial Bound)
Let f : N → R≥0 be given.
For f(n) = O(n^p) (p ∈ N_0), f has a polynomial bound.
For f(n) = 2O(n^δ) (δ ∈ R≥δ), f has an exponential bound.
Definition 5.4 (Check notes)
Definition 5.5 (Time complexity Class)
Let t : N → R≥0 be a function. The time complexity class, TIME(t(n)), is the set of all languages that are decidable by an O(t(n)) time single-tape deterministic Turing machine.
Theorem 5.1 (Deterministic Equivalence)
Let t(n) be a function such that t(n) ≥ n. For every t(n) time (deterministic) multi-tape decider there exists an equivalent O(t^2(n)) time (deterministic) single-tape decider.
Definition 5.6 (Running Time)
Let N be a nondeterministic decider. The running time of N is the function f : N → N, giving the maximum number of steps f(n) that N uses on any
branch of its computation on any input of length n.
Theorem 5.2 (Nondeterministic Decider Equivalence)
Let t(n) be a function, such that t(n) ≥ n. For every t(n) time nonderministic single-tape decider there exists an equivalent 2^O(t(n)) time deterministic singletape decider.
Definition 5.7 (Class P)
The complexity class P is the set of all languages that are decidable in polynomial time on a deterministic single-tape Turing machine, i.e. P = U[k∈N0] TIME (n^k).
Theorem 5.3 (P)
We define the problem / language P AT H by
P AT H = {(G, s, t) | G is a directed graph that has a path from s to t} .
It holds P AT H ∈ P.
Definition 5.8 (Relatively Prime)
Let x, y be natural numbers. x and y are relatively prime, if it holds for their greatest common divisor (gcd)
gcd(x, y) = 1 .
Theorem 5.4 (RELPRIME)
We define the problem / language RELP RIME by
RELP RIME = {(x, y) | x and y are relatively prime} .
It holds RELP RIME ∈ P.
Theorem 5.5 (CFG and P)
It holds ACF G ∈ P, hence every context-free language is a member of P.
Definition 5.9 (nondeterministic time complexity class)
Let t : N → R≥0 be a function. The nondeterministic time complexity class, NTIME(t(n)), is the set of all languages that are decidable by an O(t(n))
time nondeterministic single-tape Turing machine.
Definition 5.10 (The class NP)
) The complexity class NP is the set of all languages that are decidable in polynomial time by a nondeterministic single-tape Turing machine, i.e. NP = U[k∈N0] NTIME (n^k).
