This lecture

(1)

Lecture 31: Efficiency in computation

Instructor: S. Akshay

IITB, India

Spring 2020

(2)

Recap

Turing machines and computability 1. Turing machines

(i) Definition (ii) Variants

(iii) Decidable and Turing recognizable languages (iv) Church-Turing Hypothesis

2. Undecidability

(i) A proof technique by diagonalization (ii) Via reductions

3. Applications: showing (un)decidability of other problems (i) A string matching problem: Post’s Correspondance Problem (ii) A problem for compilers: Unambiguity of Context-free languages

(3)

Recap

2. Undecidability

(ii) A problem for compilers: Unambiguity of Context-free languages

(4)

Recap

2. Undecidability

3. Applications: showing (un)decidability of other problems (i) A string matching problem: Post’s Correspondance Problem (ii) A problem for compilers: Unambiguity of Context-free languages

(5)

This lecture

Efficiency in computation

I Resource bounded Turing machines I Measuring run-time complexity I Computability and complexity

I The polynomial time complexity class

Reading Material

I Section 10.1, Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani and Ullman

I Section 7.1, 7.2, Introduction to the Theory of Computation, Michael Sipser

(6)

This lecture

Efficiency in computation

In this lecture we will cover

I Resource bounded Turing machines I Measuring run-time complexity I Computability and complexity

I The polynomial time complexity class

Reading Material

I Section 10.1, Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani and Ullman

I Section 7.1, 7.2, Introduction to the Theory of Computation, Michael Sipser

(7)

Turing machines with Resource constraints

What resources do Turing machines use?

I Space/memory I Time

I Cost I Energy

I What else? number of times a state is visited, number of tape reversals, number of writes

Why consider resources? I TMs are algorithms...

I Decidability does not implementability!

(8)

Turing machines with Resource constraints

Resources for computation:

I Cost I Energy

(9)

Turing machines with Resource constraints

I Cost I Energy I What else?

(10)

Turing machines with Resource constraints

I Cost I Energy

(11)

I Cost I Energy

Why consider resources?

I TMs are algorithms...

(12)

Running Time Complexity

Given M a halting TM,running time of M is the function

f(n) :N→N, which counts the maximum number of steps that M uses on any input of length n.

(13)

Is this the only notion possible? Any others?

(14)

Running Time Complexity

I Worst-case complexity - longest running time of all inputs of lengthn (in this course, we consider this)

I Average-case complexity - average running time over all inputs of length n.

(15)

Let f,g :B→R⁺, we sayg(n) is an (asymptotic) upper bound for f(n), denoted

f(n) =O(g(n))if ∃c,n₀ ∈Z⁺ s.t∀n ≥n₀,f(n)≤c ·g(n).

I f is less than or equal to g up to a constant factor.

I why use this? to estimate instead of precise.

(16)

A recap of Big O and small o notation

Let f,g :B→R⁺, we write f(n) = o(g(n))if ∀c >0,∃n₀ s.t ∀n≥n₀, f(n)≤c·g(n), i.e., limn→∞ f(n)

g(n) = 0.

I more like strictly less than (asymptotically)

(17)

f(n) =O(g(n))if ∃c,n0 ∈Z⁺ s.t∀n ≥n0,f(n)≤c ·g(n).

g(n) = 0.

Exercises: True or false

1. 234n³+ 345n²−3 =O(n³) 2. 84n³+ 4n⁴+ 3 =O(n⁵) 3. n=o(nloglogn)

4. 2^O⁽ⁿ⁾ =o(n^242345325)

5. O(n) +ⁿO(n) +O(n) =O(n²)

(18)

A recap of Big O and small o notation

g(n) = 0.

Exercises: True or false

1. 234n³+ 345n²−3 =O(n³) 2. 84n³+ 4n⁴+ 3 =O(n⁵) 3. n=o(nloglogn)

4. 2^O⁽ⁿ⁾ =o(n^242345325)

5. O(n) +ⁿ₂O(n) +O(n) =O(n²)

polynomial: n^c for c >0, exponential: 2ⁿ^δ,δ >0.

(19)

Let t :N→R⁺. A language L⊆Σ^∗ is said to be in TIME(t(n))if there exists a deterministic (halting) Turing machine M such that ∀x ∈Σ^∗ of length n,M halts on x within time O(t(n)).

(20)

Running Time Complexity

TIME(t(n))is set of all languages decidable by a O(t(n)) TM

(21)

Exercise: Is A={0^k1^k |k ≥0}in O(n²)?

(22)

Running Time Complexity

1. scan tape once to check if input is of form 0^∗1^∗. else reject.

2. repeat until there are no 0’s:

3. scan tape to cross a single 0 and single 1 (if you cant find 1 to cross off, reject)

4. at end if there are 1’s remaining reject, otherwise, accept.

(23)

1. scan tape once to check if input is of form 0^∗1^∗. else reject.O(n) steps 2. repeat until there are no 0’s:

3. scan tape to cross a single 0 and single 1 (if you cant find 1 to cross off, reject)

(24)

Running Time Complexity

1. scan tape once to check if input is of form 0^∗1^∗. else reject.O(n) steps 2. repeat until there are no 0’s:

3. scan tape to cross a single 0 and single 1 (if you cant find 1 to cross off, reject)O(n) steps

(25)

1. scan tape once to check if input is of form 0^∗1^∗. else reject.O(n) steps 2. repeat until there are no 0’s: n/2 repetitions

(26)

Running Time Complexity

4. at end if there are 1’s remaining reject, otherwise, accept. O(n) steps

(27)

4. at end if there are 1’s remaining reject, otherwise, accept. O(n) steps Overall: O(n) +ⁿO(n) +O(n) =O(n²) steps

(28)

Running Time Complexity (Contd.)

TIME(t(n))is set of all languages decidable by a O(t(n)) Turing machine

Questions

I IsA={0^k1^k |k ≥0}in o(n²)?

I IsA in O(n)?

(29)

Questions

I IsA={0^k1^k |k ≥0}in o(n²)?

I IsA in O(n)?

Does crossing two 0s and 1s on every scan instead of just one help?

(30)

Running Time Complexity (Contd.)

Questions

I IsA={0^k1^k |k ≥0}in o(n²)?

I IsA in O(n)?

I Scan tape and reject, if 0 is to right of 1.

I Scan the 0s and copy them to another tape, until first 1.

I Scan 1s in first tape together with 0s in second tape, if 0’s are crossed before 1s are read, reject

I if all 0s are crossed off at the end, accept, else reject.

(31)

Questions

I IsA={0^k1^k |k ≥0}in o(n²)?

I IsA in O(n)?

(32)

Running Time Complexity (Contd.)

TIME(t(n))is set of all languages decidable by a O(t(n))1-tapeTuring machine

Questions

I (HW)Is A={0^k1^k |k ≥0}in o(n²)?

I IsA in O(n)?

So, with 2-tape can improve “complexity”. Can we improve with 1-tape?

(33)

Questions

I (HW)Is A={0^k1^k |k ≥0}in o(n²)?

I (Challenge)IsA in O(n)?

So, with 2-tape can improve “complexity”.

(34)

Running Time Complexity (Contd.)

Questions

I (HW)Is A={0^k1^k |k ≥0}in o(n²)?

I (Challenge)IsA in O(n)?

So, with 2-tape can improve “complexity”.

Conclusion: change of model can change complexity, even if it does not change computability.

(35)

Computability vs Complexity

I Computability: (Church Turing Hypothesis) All reasonable models of computation are equivalent, i.e., they decide the same class of languages.

I Complexity: Choice of model affects running time.

(36)

Complexity between models of computation

Our goal

(37)

Our goal

I to measure or classify problems by their (running) time complexity

(38)

Complexity between models of computation

Our goal

I to measure or classify problems by their (running) time complexity I But if change of model changes complexity, then how can we measure or

classify them?

(39)

Our goal

classify them?

I Fortunately, it doesn’t change by much, at least for deterministic models!

(40)

Complexity between models of computation

Our goal

classify them?

I Fortunately, it doesn’t change by much, at least for deterministic models!

Theorem

Let t(n) be a function such that t(n)≥n. Then everyt(n) time multitape det TM has an equivalent O(t²(n)) time 1-tape det TM.

(41)

Theorem

(42)

Multi-tape to single tape

Theorem

Proof: Given k-tape TM M running in t(n) time, define 1-tape TMS:

(43)

Theorem

Proof: Given k-tape TM M running in t(n) time, define 1-tape TMS: I Storek-tapes ofM in 1-tape of S, with head positions marked.

I To simulate one-step of M,

(44)

Multi-tape to single tape

Theorem

Proof: Given k-tape TM M running in t(n) time, define 1-tape TMS: I Storek-tapes ofM in 1-tape of S, with head positions marked.

I To simulate one-step of M,

I S scans all info on its tape to check all head positions

I then makes another pass over tape to update tape contents and head positions.

I If some head moves rightward into previously unread portion of tape inM, then inS, space allocated for that tape is increased by a right-shift of all content to right.

(45)

Theorem

Proof: Given k-tape TM M running in t(n) time, define 1-tape TMS: I Storek-tapes ofM in 1-tape of S, with head positions marked.O(n) I To simulate one-step of M,

I S scans all info on its tape to check all head positions O(t(n))steps I then makes another pass over tape to update tape contents and head

positions. O(t(n))steps

I If some head moves rightward into previously unread portion of tape inM, then inS, space allocated for that tape is increased by a right-shift of all content to right.

(46)

Multi-tape to single tape

Theorem

Proof: Given k-tape TM M running in t(n) time, define 1-tape TMS: I Storek-tapes ofM in 1-tape of S, with head positions marked.O(n) I To simulate one-step of M,

I If some head moves rightward into previously unread portion of tape inM, then inS, space allocated for that tape is increased by a right-shift of all content to right. k tapes =k heads=k×O(t(n))steps

(47)

Theorem

Proof: Given k-tape TM M running in t(n) time, define 1-tape TMS: I Storek-tapes ofM in 1-tape of S, with head positions marked.O(n) I To simulate one-step of M,O(t(n))

(48)

Multi-tape to single tape

Theorem

I t(n) steps ofM impliest(n)×O(t(n)) =O(t²(n)) steps

(49)

Theorem

I t(n) steps ofM impliest(n)×O(t(n)) =O(t²(n)) steps I Overall: O(n) +O(t²(n)) =O(t²(n)) (since t(n)≥n)

(50)

What about non-determinism?

Running time of a non-det halting TM

The running time of a non-det halting TM N is the function f(n:N→N), where f(n) is the max number of steps that N uses on any branch of its computation on any input of length n.

Theorem

Lett(n) be a function such that t(n)≥n. Then everyt(n) time non-det 1-tape TMN has an equivalent2^O^(t(n)) timedet 1-tape TMD.

I Recall that computation of N is viewed as a tree. I Each branch is of length at most t(n).

I What is the max number of leaves of the tree? b^t(n) where b is from transition fn.

I What is the max number of nodes of tree?less than twice no. of leaves. I Do bfs on tree – what is the complexity of this? O(b^t(n)) = 2Ô(t(n)). I three tapes to one-tape: (2Ô(t(n)))² = 2Ô(t(n)).

(51)

What about non-determinism?

Theorem

Let t(n) be a function such that t(n)≥n. Then everyt(n) time non-det 1-tape TM N has an equivalent2^O^(t(n)) timedet 1-tape TMD.

I Each branch is of length at most t(n).

(52)

What about non-determinism?

Theorem

I Recall that computation of N is viewed as a tree.

I What is the max number of leaves of the tree?

b^t(n) where b is from transition fn.

(53)

What about non-determinism?

Theorem

I What is the max number of nodes of tree?

I Do bfs on tree – what is the complexity of this? O(b ) = 2 . I three tapes to one-tape: (2^O(t(n)))² = 2^O(t(n)).

(54)

What about non-determinism?

Theorem

I What is the max number of nodes of tree?less than twice no. of leaves.

I Do bfs on tree – what is the complexity of this?

O(b^t(n)) = 2Ô(t(n)). I three tapes to one-tape: (2Ô(t(n)))² = 2Ô(t(n)).

(55)

Theorem

I What is the max number of nodes of tree?less than twice no. of leaves.

I Do bfs on tree – what is the complexity of this? O(b^t(n)) = 2^O(t(n)).

(56)

The class P

So, k-tape to 1-tape involves a polynomial blow-up, while non-det to det requires an exponential blow-up.

Definition

P is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine, i.e.,

P =[

k

TIME(n^k)

Why important

I take all models of computation that are polytime eq to det 1-tape TM, P is invariant.

I classically considered to be the good class for a computer. Examples:

I Given a graph G, is there a path froms to t? I Are two given numbers relatively prime?

(57)

The class P

So, k-tape to 1-tape involves a polynomial blow-up, while non-det to det requires an exponential blow-up.

Definition

P =[

k

TIME(n^k)

Why important

I classically considered to be the good class for a computer.

I Are two given numbers relatively prime?

(58)

The class P

Definition

P =[

k

TIME(n^k)

Why important

Examples:

I Given a graph G, is there a path froms to t?

I Are two given numbers relatively prime?

(59)

Definition

P =[

k

TIME(n^k)

Why important

Examples:

I Given a graph G, is there a path froms to t?

(60)

Examples of problems in P

PATH: Given directed graph G = (V,E) and nodes s,t, is there a path between s and t

(61)

Brute force algo?

(62)

Examples of problems in P

I Mark s

I Repeat until no additional nodes are marked:

I scan all edges ofG and if (a,b) is an edge with amarked andb unmarked, then markb,

I if t is marked, accept, else reject.

(63)

I Mark s

I Repeat until no additional nodes are marked: at most|V|times I scan all edges ofG and if (a,b) is an edge with amarked andb

unmarked, then markb,

I if t is marked, accept, else reject.

(64)

Examples of problems in P

RELPRIME: Given x,y ∈N, is gcd(x,y) = 1

(65)

RELPRIME: Given x,y ∈N, is gcd(x,y) = 1 Euclid’s algo!

I repeat till y= 0;

I assign x:=x mod y I exchange x and y;

I At end if result is x= 1 accept, else reject.

(66)

Examples of problems in P

RELPRIME: Given x,y ∈N, is gcd(x,y) = 1 Euclid’s algo!

I repeat till y= 0;how many times is this done?

I assign x:=x mod y I exchange x and y;

I At end if result is x= 1 accept, else reject.

(67)

The class EXP

Definition

EXP is the class of languages that are decidable in exponential time on a deterministic single-tape Turing machine, i.e.,

EXP =[

k

TIME(2ⁿ^k)

I AllP time problems! i.e.,P ⊆EXP.

I HAMILTONIAN-PATH: G,s,t: is there a path froms tot that goes through each node of G exactly once?

I (Generalized) CHESS

I COMPOSITIES: is a number composite?

(68)

The class EXP

Definition

EXP =[

k

TIME(2ⁿ^k)

Examples

(69)

The class EXP

Definition

EXP =[

k

TIME(2ⁿ^k)

Examples

(70)

The class EXP

Definition

EXP =[

k

TIME(2ⁿ^k)

Examples

(71)

The class EXP

Definition

EXP =[

k

TIME(2ⁿ^k)

Examples

(72)

The class EXP

Definition

EXP =[

k

TIME(2ⁿ^k)

Examples