4.2 Space's Complexity, Growth Rate of Functions, Complexity Classes

What is the space complexity of a (possibly deterministic) Turing Machine M?

The function:
s_M: N → N where s_M(n)

Where s_M(n) is the maximum number of tape squares M can visit on any input of length n.

What is the maximum number of tape squares in multitape TMs?

The maximum of the numbers for the individual tapes (which differs only by a constant factor from the maximal number of squares visited on all tapes together)

Given f, g: N → R⁺ when is f of order g?

If there are positive integers c and n₀ such that f(n) ≤ c · g (n) for all n ≥ n₀.

What is the class of all functions of order g denoted by, and what is the relevance to f?

O(g), so f ∈ O(g)

Given there is a TM M’ for every k-tape TM M, what is L(M’)

L(M’) = L(M) and τ_M’ ∈ O(τ²_M)

What does the theorem “There are arbitrarily complex languages” state?

Let f: N→N be a total computable function.

Then there exists a decidable language L such that for every Turing Machine M accepting L, the time complexity t_M​ is not bounded by f.

In other words, there are decidable languages that are arbitrarily complex — no computable function can bound their time complexity.

What does the theorem “There need not exist a fastest Turing Machine” state?

There exists a decidable language L such that for every Turing Machine M accepting L, there exists another Turing Machine M′ with:

L(M′)=L(M)

and 

τ_M′​∈O(log₂​(τ_M​))

When is a language L decidable in polynomial time?

If there is a Turing Machine M deciding L such that τ_M ∈ O(n^r) for some r ∈ N. The class of all languages decidable in polynomial time is denoted by P.

When is a language L decidable in polynomial space?

If there is a Turing Machine M deciding L such that s_M ∈ O(n^r) for some r ∈ N. The class of all languages decidable in polynomial space is denoted by PSpace.

What is a path in terms of graphs?

A sequence of nodes connected by edges

What is the path problem?

Input: A graph G and nodes s and t
Question: Does G have a path from s to t

What is the algorithm that solves the path problem?

Marks all nodes that are reachable from node s:

When is a language L accepted in nondeterministic polynomial time?

If there is a nondeterministic TM N accepting L such that τ_N ∈ O(n^r) for some r ∈ N. The class of all languages that are accepted in nondeterministic polynomial time is denoted by NP.

When is a language L accepted in nondeterministic polynomial space?

If there is a NTM N accepting L such that s_N ∈ O(n^r) for some r ∈ N. The class of all languages that are accepted in nondeterministic polynomial space is denoted by NPSpace.

What is a complete graph?

A graph in which each 2 nodes are connected by an edge.

Define the complete subgraph problem

Input: A graph G and k >= 1
Question: Does G have a complete subgraph with k vertices?

What is a Hamiltonian circuit?

A path v0,….,vn through all nodes of a graph such that v0 = vn and v1,….,vn are pairwise distinct.

What is the Hamiltonian cicuit problem?

Input: A graph C
Question: Does G have a Hamiltonian circuit