5: Complexity

Question 1

What is an oracle?

Answer 1

A black box that is used with TMs that answer or solve difficult problems in one call.

Question 2

What is a computation resource? List 5.

Answer 2

An asset that enables computations of increased complexity and difficulty.

time; space; energy; the number of comparisons; the number of calls to an oracle.

Question 3

How do you measure time and space complexity in TMs?

Answer 3

Time ≡ the number of transitions made by TM.

Space ≡ the number of tape cells touched by TM.

Question 4

What is an instance of a problem?

Answer 4

An input word that falls within (the language of) a problem.

Question 5

Consider a positive non-decreasing function 𝑓 ∶ N → N, 𝐿 a language, L, (over some alphabet 𝐴),
and 𝑛 being the length of the input to f(n).

True/false: DTIME(𝑓 (𝑛)) > {𝐿 | 𝐿 is decided by some (deterministic) TM in at most 𝑓 (𝑛) transitions}

Answer 5

False. Here, DTIME(𝑓 (𝑛)) = {𝐿 | 𝐿 is decided by some (deterministic) TM in at most 𝑓(𝑛) transitions}

Question 6

What is a complexity class?

Answer 6

A set of computing problems, grouped by the time and space complexities that they require to solve.

Question 7

How do you determine the complexity class(es) of languages?

Answer 7

Consider how the number of transitions and tape cells/stack size needed changes asymptotically for inputs of different length into machines recognising the language. You can do so for both deterministic and nondeterministic machines and find for either or both if the language lies within (takes to solve) constant, linear, polynomial, logarithmic, exponential, etc, time.

Question 8

What does ∈^? mean?

Answer 8

A ∈^? B = whether A is an element of the set B. (?)

Question 9

What does the big O notation mean?

Answer 9

• If 𝑓 (𝑛) = 𝑂(𝑔(𝑛)), then 𝑔 is at least as big as 𝑓
• 𝑓 is at most a constant times 𝑔
• ∃𝑐 > 0, 𝑛0. ∀𝑛 > 𝑛0. 𝑓 (𝑛) < 𝑐𝑔(𝑛)

Question 10

What does the little o notation mean?

Answer 10

• If 𝑓 (𝑛) = 𝑜(𝑔(𝑛)), then 𝑓 is infinitely smaller than 𝑔
• 𝑓 (𝑛)/𝑔(𝑛) = 0
• ∀𝜖 > 0.∃𝑛𝜖. ∀𝑛 > 𝑛𝜖. 𝑓 (𝑛) < 𝜖𝑔(𝑛)

Question 11

What does the big omega notation mean?

Answer 11

• If 𝑓 (𝑛) = Ω(𝑔(𝑛)), then 𝑓 is at least as big as 𝑔
• 𝑓 is at least a constant times 𝑔
• 𝑔 = 𝑂(𝑓 (𝑛))

Question 12

What does the little omega notation mean?

Answer 12

• If 𝑓 (𝑛) = 𝜔(𝑔(𝑛)), then 𝑓 is infinitely smaller than 𝑔
• 𝑔(𝑛)/𝑓 (𝑛) = 0
• 𝑔 = 𝑜(𝑓 (𝑛))

Question 13

What does the big theta notation mean?

Answer 13

• If 𝑓 (𝑛) = Θ(𝑔(𝑛)), then 𝑓 and 𝑔 are the same size
• 𝑓 and 𝑔 are within a constant factor
• 𝑓 = 𝑂(𝑔(𝑛)) and 𝑓 = Ω(𝑔(𝑛))

Question 14

Consider a positive non-decreasing function 𝑓 ∶ N → N, 𝐿 a language, L, (over some alphabet 𝐴),
and 𝑛 being the length of the input to f(n).

True/false: DSPACE(𝑓 (𝑛)) > {𝐿 | 𝐿 is decided by some (deterministic) TM in at most 𝑓 (𝑛) tape cells}

Answer 14

False. Here, DSPACE(𝑓 (𝑛)) = {𝐿 | 𝐿 is decided by some (deterministic) TM in at most 𝑓 (𝑛) tape cells}

Question 15

Are input tape cells (or whole tapes dedicated to holding input in multi-tape TMs) counted as part of space complexity? Why?

Answer 15

No. So the space complexity represents the number of tape cells to solve a problem: cells to take input are not part of those cells.

Question 16

When is 𝑇(𝑛) 𝑂(𝑓 (𝑛))?

Answer 16

There exist constants 𝑐 and a 𝑛0 > 0 such that for all 𝑛 > 𝑛0, 𝑇(𝑛) ≤ 𝑐 ⋅ 𝑓 (𝑛). Intuitively, 𝑇(𝑛) grows no more than 𝑓 (𝑛) for large 𝑛. This is an asymptotic upper bound.

Question 17

When is 𝑇(𝑛) o(𝑓 (𝑛))?

Answer 17

For every 𝑐 > 0 there exists a 𝑛0 > 0 such that for all 𝑛 > 𝑛0, 𝑇(𝑛) ≤ 𝑐 ⋅ 𝑓 (𝑛). Intuitively, 𝑇(𝑛) grows strictly slower than 𝑓 (𝑛) for large 𝑛. This is an asymptotic upper bound.

Question 18

When is 𝑇(𝑛) Ω(𝑓 (𝑛))?

Answer 18

There exist constants 𝑐 and a 𝑛0 > 0 such that for all 𝑛 > 𝑛0, 𝑇(𝑛) ≥ 𝑐 ⋅ 𝑓 (𝑛). Intuitively, 𝑇(𝑛) grows no less than 𝑓 (𝑛) for large 𝑛. This is an asymptotic lower bound.

Question 19

When is 𝑇(𝑛) ω(𝑓 (𝑛))?

Answer 19

For every 𝑐 > 0 there exists a 𝑛0 > 0 such that for all 𝑛 > 𝑛0, 𝑇(𝑛) ≥ 𝑐 ⋅ 𝑓 (𝑛). Intuitively, 𝑇(𝑛) grows strictly faster than 𝑓 (𝑛) for large 𝑛. This is an asymptotic lower bound.

Question 20

When is 𝑇(𝑛) Θ(𝑓 (𝑛))?

Answer 20

There exist constants 𝑐1, 𝑐2, and a 𝑛0 > 0 such that for all 𝑛 > 𝑛0, 𝑐1⋅ 𝑓 (𝑛) ≤ 𝑇(𝑛) ≤ 𝑐2⋅ 𝑓 (𝑛). Intuitively,𝑇(𝑛) grows like 𝑓 (𝑛) for large 𝑛. This is an asymptotic tight bound.

Question 21

What is the Time Speedup Lemma?

Answer 21

Let 𝐿 ∈ DTIME(𝑓 (𝑛)). Then, for any 𝑐 > 0,
𝐿 ∈ DTIME(𝑓 ′(𝑛)) where 𝑓′(𝑛) = 𝑐𝑓 (𝑛) + 𝑂(𝑛).

If you increase the number of states and alphabet size (by a constant factor depending on 𝑐), so that the new TM can make ≥ 𝑐 transitions for each transition of the original TM, then in 𝑂(𝑛) time, we can encode the original input.

Question 22

What is the Tape Compression Lemma?

Answer 22

Let 𝐿 ∈ DSPACE(𝑓 (𝑛)). Then, for any 𝑐 > 0,
𝐿 ∈ DSPACE(𝑓 ′(𝑛))where 𝑓′(𝑛) = 𝑐𝑓 (𝑛) + 𝑂(1).

If you increase the number of states and alphabet (by a constant factor depending on 𝑐), the new TM can use ≥ 𝑐 cells for each tape cell used of the original TM.

Question 23

Let 𝑓 be a positive non-decreasing function 𝑓 ∶ N → N
Let 𝐿 be a language (over some alphabet 𝐴),
and 𝑛 be the length of the input.

True/false: NTIME(𝑓 (𝑛)) = {𝐿 ∣ There is some nondeterministic TM 𝑀 such that for any word 𝑤 ∈ 𝐿, any computation path takes at most 𝑓 (𝑛) transitions}

Answer 23

True.

Question 24

Let 𝑓 be a positive non-decreasing function 𝑓 ∶ N → N
Let 𝐿 be a language (over some alphabet 𝐴),
and 𝑛 be the length of the input.

True/false: NSPACE(𝑓 (𝑛)) = {𝐿 ∣ There is some nondeterministic TM 𝑀 such that for any word 𝑤 ∈ 𝐿, any computation path takes at most 𝑓 (𝑛) additional tape cells}

Answer 24

True.

Question 25

Let 𝑓 be a positive non-decreasing function 𝑓 ∶ N → N
Let 𝐿 be a language (over some alphabet 𝐴),
and 𝑛 be the length of the input.

True/false: NSPACE(𝑓 (𝑛)) = {𝐿 ∣ There is some certificate 𝑐 such that 𝐿 is decided by a Deterministic TM which takes 𝑐 as additional input using at most 𝑓 (𝑛) additional tape cells}

Answer 25

True.

Question 26

Let 𝑓 be a positive non-decreasing function 𝑓 ∶ N → N
Let 𝐿 be a language (over some alphabet 𝐴),
and 𝑛 be the length of the input.

True/false: NTIME(𝑓 (𝑛)) = {𝐿 ∣ There is some certificate 𝑐 such that 𝐿 is decided by a Deterministic TM which takes 𝑐 as additional input using at most 𝑓 (𝑛) transitions}

Answer 26

True.

Question 27

How can you define DTIME?

Answer 27

Consider a positive non-decreasing function 𝑓 ∶ N → N, 𝐿 a language, L, (over some alphabet 𝐴),
and 𝑛 being the length of the input to f(n).

DTIME(𝑓 (𝑛)) = {𝐿 | 𝐿 is decided by some (deterministic) TM in at most 𝑓(𝑛) transitions}

Question 28

How can you define DSPACE?

Answer 28

Consider a positive non-decreasing function 𝑓 ∶ N → N, 𝐿 a language, L, (over some alphabet 𝐴),
and 𝑛 being the length of the input to f(n).

DSPACE(𝑓 (𝑛)) = {𝐿 | 𝐿 is decided by some (deterministic) TM in at most 𝑓 (𝑛) tape cells}

Question 29

How can you define NTIME?

Answer 29

Let 𝑓 be a positive non-decreasing function 𝑓 ∶ N → N
Let 𝐿 be a language (over some alphabet 𝐴),
and 𝑛 be the length of the input.

NTIME(𝑓 (𝑛)) = {𝐿 ∣ There is some certificate 𝑐 such that 𝐿 is decided by a Deterministic TM which takes 𝑐 as additional input using at most 𝑓 (𝑛) transitions}

AND

NTIME(𝑓 (𝑛)) = {𝐿 ∣ There is some nondeterministic TM 𝑀 such that for any word 𝑤 ∈ 𝐿, any computation path takes at most 𝑓 (𝑛) transitions}

Question 30

How can you define NSPACE?

Answer 30

Let 𝑓 be a positive non-decreasing function 𝑓 ∶ N → N
Let 𝐿 be a language (over some alphabet 𝐴),
and 𝑛 be the length of the input.

NSPACE(𝑓 (𝑛)) = {𝐿 ∣ There is some nondeterministic TM 𝑀 such that for any word 𝑤 ∈ 𝐿, any computation path takes at most 𝑓 (𝑛) additional tape cells}

AND

True/false: NSPACE(𝑓 (𝑛)) = {𝐿 ∣ There is some certificate 𝑐 such that 𝐿 is decided by a Deterministic TM which takes 𝑐 as additional input using at most 𝑓 (𝑛) additional tape cells}

Question 31

Within which time and space complexities can you copy an input from an input tape to a working tape in a multi-tape TM? How could you improve this for the language 𝐿(0 ^ (2 ^ 𝑚))?

Answer 31

Copying across would take DTIME(2𝑛 log2(𝑛)) and DSPACE(𝑛).

You could instead have a binary number to count the number of input symbols on the working tape, incrementing it every time you read a new input symbol. Since the language is a number of 0s equal to a power of 2, after reading them all the working tape will consist of a 1 and all 0s afterwards. This improves space complexity to DSPACE(log2(𝑛)) and time complexity to ??.

Question 32

When finding complexity classes with nondeterministic computation, do we take the worst, best, or average computational path, in terms of complexity/

Answer 32

Use the worst-case paths.

Question 33

What is the time hierarchy theorem?

Answer 33

The idea that you can increase the computational power of a system by increasing its time complexity.

For a time-constructible function f(n),

Let f(n) * log(f(n)) = o(g(n)).

Then DTIME(g(n)) \ DTIME(f(n)) ≠ ∅

So there are more problems that can be done in f(n) time that can’t be done in g(n) time if f(n) is time-constructible and f(n) > g(n) + log(n).

Question 34

What does it mean for a function to be time-constructible?

Answer 34

A function, f(n), is called time constructible if there is a TM, which given the string 1 ^ n as input stops, with f(n) on its tape (in binary) after f(n) transitions (time). If a function is o(n) then it cannot be time constructible.

Question 35

What is diagonalisation, and Cantor’s diagonalisation method?

Answer 35

Diagonalisation is when you take a matrix or set, and build a new row in which every ith element is different from the ith element in the ith row (so complement of a bit if binary).

Cantor applied diagonalisation to show that the matrix of all infinite binary sequences is infinite (uncountable) since the new row from diagonalisation will be different from every other row. Assuming the set is countable, you should be able to enumerate all its elements as s0 to sn as described but the new row made by diagonalisation contradicts this as it is not in the set, proving the set of all binary sequences to be uncountable and infinite by proof by contradiction.

Question 36

What is the proof for the Time Hierarchy Theorem?

Answer 36

??

Question 37

What is the Space Hierarchy Theorem?

Answer 37

Any increases in asymptotic space increases a system’s computational power.

Let f(n) = o(g(n)), where f(n) is space-constructible.

Then DSPACE(g(n)) \ DSPACE(f(n)) ≠ ∅

So there are more problems that can be done in f(n) space that can’t be done in g(n) space if f(n) is space-constructible and f(n) > g(n).

Question 38

What does it mean for a function to be space-constructible?

Answer 38

A function, f(n), is called space-constructible if there is a TM, which given the string 1 ^ n as input stops with f(n) on its tape (in binary) while using f(n) tape cells (space).

Question 39

What is the proof for the Space Hierarchy Theorem?

Answer 39

??

Question 40

What are the consequences of the Time and Space Hierarchy Theorems

Answer 40

• DTIME(n ^ 2) is strictly more powerful than DTIME(n)
• DTIME(n ^ 1042) is strictly more powerful than DTIME(n ^ 1041)
• If d > c >= 1, DTIME(n ^ d) is strictly more powerful than DTIME(n ^ c).
• DTIME(n ^ π) is strictly more powerful than DTIME(n ^ e) since π > e.
• DSPACE(n * log(n)) is strictly more powerful than DSPACE(n).
• DTIME(2 ^ n) is strictly more powerful than DTIME(n ^ 3)
• Much more time (or space) means more problems solvable

Question 41

How are DSPACE and NSPACE related?

Answer 41

DSPACE(𝑓 (𝑛)) ⊆ NSPACE(𝑓 (𝑛))

Question 42

How are DTIME and NTIME related?

Answer 42

DTIME(𝑓 (𝑛)) ⊆ NTIME(𝑓 (𝑛))

Question 43

How do you mathematically define deterministic polynomial time complexities?

Answer 43

P = ∪ 𝑘≥1 DTIME(𝑛^𝑘)

So the union of all factors raised to some k where k >= 1

Question 44

How do you mathematically define deterministic exponential time complexities?

Answer 44

EXP = ∪ 𝑘≥1 DTIME(2^ (𝑛 ^ 𝑘))

So some factor raised to some variable in turn raised to some constant

Question 45

Why and how are the polynomial and exponential time complexity classes different?

Answer 45

In polynomial, the factor is raised to a constant k; in exponential, the factor is raised to a variable n that is itself raised to a constant k.

Question 46

How do you mathematically define deterministic logarithmic space complexities?

Answer 46

L = DSPACE(log 𝑛)

Question 47

What is NPSPACE?

Answer 47

nondeterministic polynomial space complexity

Question 48

How can you mathematically relate NPSPACE and DSPACE?

Answer 48

PSPACE = ∪ 𝑘≥1 DSPACE(𝑛^𝑘)

Question 49

True/false: P problems ⊂ EXP problems.

Answer 49

True.

Question 50

Prove that P problems ⊂ EXP problems.

Answer 50

??

Question 51

How are the larger complexity classes related?

Answer 51

P ⊊ EXP
NP ⊊ NEXP
L ⊊ PSPACE ⊊ EXPSPACE

P ⊆ NP
PSPACE ⊆ NPSPACE
EXP ⊆ NEXP

Question 52

What is the Non-deterministic Time Hierarchy Theorem?

Answer 52

Let𝑓 (𝑛 + 1) log 𝑓 (𝑛 + 1) = 𝑜(𝑔(𝑛)).

Then NTIME(𝑔(𝑛)) \ NTIME(𝑓 (𝑛)) ≠ ∅

Question 53

What is the Non-deterministic Space Hierarchy Theorem?

Answer 53

Let𝑓 (𝑛) = 𝑜(𝑔(𝑛)).

Then NSPACE(𝑔(𝑛)) \ NSPACE(𝑓 (𝑛)) ≠ ∅

Question 54

How can you relate time and space complexities?

Answer 54

NTIME(𝑓 (𝑛)) ⊆ DSPACE(𝑓 (𝑛))

AND

NSPACE(𝑓 (𝑛)) ⊆ ∪𝑐DTIME(𝑐𝑓 (𝑛))

Question 55

Prove NTIME(𝑓 (𝑛)) ⊆ DSPACE(𝑓 (𝑛))

Answer 55

??

Question 56

How can you relate space and time, determinism and non-determinism?

Answer 56

DTIME(𝑓 (𝑛) ⊆ NTIME(𝑓 (𝑛)) ⊆ DSPACE(𝑓 (𝑛))

P ⊆ NP ⊆ PSPACE

AND

DTIME(𝑓 (𝑛)) ⊆ NTIME(𝑓 (𝑛)) ⊆ DSPACE(𝑓 (𝑛))
⊆ NSPACE(𝑓 (𝑛)) ⊆ DTIME(2𝑂(𝑓 (𝑛)))

P ⊆ NP ⊆ PSPACE ⊆ NPSPACE ⊆ EXP

Question 57

Prove NSPACE(𝑓 (𝑛)) ⊆ ∪𝑐DTIME(𝑐𝑓 (𝑛))

Answer 57

??

Question 58

How can you relate Non-deterministic vs Deterministic Space?

Answer 58

Let𝑓 (𝑛) ≥ log 𝑛. Then

NSPACE(𝑓 (𝑛)) ⊆ DSPACE((𝑓 (𝑛))^ 2)

Question 59

Prove NSPACE(𝑓 (𝑛)) ⊆ DSPACE((𝑓 (𝑛))^ 2)

Answer 59

??

Question 60

How can you relate Nondeterministic vs Deterministic Time?

Answer 60

NP ⊆ EXP

P ⊆ NP

Question 61

Can you get additional power by adding a constant amount of time and/or space?

Answer 61

No.

Question 62

What happens when adding a “large” amount of time and/or space?

Answer 62

Adding a “large” amount of time and/or space gives a strict hierarchy of complexity classes.

Question 63

Can we relate complexity classes (time vs space)?

Answer 63

Yes, some.

Question 64

True/false: All regular languages are DSPACE(1).

Answer 64

True.

Question 65

What is the significance of all regular languages being DSPACE(1)?

Answer 65

Don’t need any more tape cells than those used by the input word. They’re recognised by DFAs, which have no memory and so can be turned into TMs that recognise the same language using tape cells only also used to take input.