5: Complexity Flashcards

Question 1

Q

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

A

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 2

Q

What is a computation resource? List 5.

Answer

A

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

Q

How do you measure time and space complexity in TMs?

Answer

A

Time ≡ the number of transitions made by TM.

Space ≡ the number of tape cells touched by TM.

Question 4

Q

What is an instance of a problem?

Answer

A

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

Question 5

Q

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

A

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

Question 6

Q

What is a complexity class?

Answer

A

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

Question 7

Q

How do you mathematically define deterministic polynomial time complexities?

Answer

A

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

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

Question 8

Q

What does ∈^? mean?

Answer

A

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

Question 9

Q

What are the consequences of the Time and Space Hierarchy Theorems

Answer

A

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 10

Q

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

Answer

A

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

Question 11

Q

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}

Question 12

Q

What is the Space Hierarchy Theorem?

Answer

A

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 13

Q

What does the big theta notation mean?

Answer

A

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

Question 14

Q

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

A

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

Question 15

Q

How can you relate time and space complexities?

Answer

A

NTIME(𝑓 (𝑛)) ⊆ DSPACE(𝑓 (𝑛))
AND
NSPACE(𝑓 (𝑛)) ⊆ ∪𝑐DTIME(𝑐𝑓 (𝑛))

Question 16

Q

How can you relate Non-deterministic vs Deterministic Space?

Answer

A

Let𝑓 (𝑛) ≥ log 𝑛. Then

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

Question 17

Q

How can you mathematically relate NPSPACE and DSPACE?

Answer

A

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

Question 18

Q

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

Answer

A

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

Q

True/false: P problems ⊂ EXP problems.

Question 20

Q

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

Answer

A

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

Q

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

Question 22

Q

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

Question 23

Q

What is the Non-deterministic Space Hierarchy Theorem?

Answer

A

Let𝑓 (𝑛) = 𝑜(𝑔(𝑛)).
Then NSPACE(𝑔(𝑛)) \ NSPACE(𝑓 (𝑛)) ≠ ∅

Question 24

Q

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}

Question 25

Q

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

Answer

A

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.

Question 26

Q

How can you define NTIME?

Answer

A

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 27

Q

How can you define NSPACE?

Answer

A

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 28

Q

What is diagonalisation, and Cantor’s diagonalisation method?

Answer

A

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 29

Q

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

Answer

A

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 30

Q

What is the proof for the Time Hierarchy Theorem?

Question 31

Q

How do you mathematically define deterministic exponential time complexities?

Answer

A

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

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

Question 32

Q

What is NPSPACE?

Answer

A

nondeterministic polynomial space complexity

Question 33

Q

How are DSPACE and NSPACE related?

Answer

A

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

Question 34

Q

How are DTIME and NTIME related?

Answer

A

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

Question 35

Q

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

Answer

A

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 36

Q

How do you mathematically define deterministic logarithmic space complexities?

Answer

A

L = DSPACE(log 𝑛)

Question 37

Q

Prove that P problems ⊂ EXP problems.

Question 38

Q

How are the larger complexity classes related?

Answer

A

P ⊊ EXP
NP ⊊ NEXP
L ⊊ PSPACE ⊊ EXPSPACE
P ⊆ NP
PSPACE ⊆ NPSPACE
EXP ⊆ NEXP

Question 39

Q

What is the Non-deterministic Time Hierarchy Theorem?

Answer

A

Let𝑓 (𝑛   1) log 𝑓 (𝑛   1) = 𝑜(𝑔(𝑛)).
Then NTIME(𝑔(𝑛)) \ NTIME(𝑓 (𝑛)) ≠ ∅

Question 40

Q

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

Answer

A

DTIME(𝑓 (𝑛) ⊆ NTIME(𝑓 (𝑛)) ⊆ DSPACE(𝑓 (𝑛))
P ⊆ NP ⊆ PSPACE
AND
DTIME(𝑓 (𝑛)) ⊆ NTIME(𝑓 (𝑛)) ⊆ DSPACE(𝑓 (𝑛))
⊆ NSPACE(𝑓 (𝑛)) ⊆ DTIME(2𝑂(𝑓 (𝑛)))
P ⊆ NP ⊆ PSPACE ⊆ NPSPACE ⊆ EXP

Question 41

Q

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

Question 42

Q

How can you relate Nondeterministic vs Deterministic Time?

Answer

A

NP ⊆ EXP

P ⊆ NP

Question 43

Q

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

Question 44

Q

Can we relate complexity classes (time vs space)?

Answer

A

Yes, some.

Question 45

Q

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