Time Complexity Fall 2006 Costas Busch - RPI 1 Consider a deterministic Turing MachineM which decides a language L Fall 2006 Costas Busch - RPI
2 For any string w the computation ofM terminates in a finite amount of transitions Initial state Fall 2006 Accept or Reject w Costas Busch - RPI 3
Decision Time = #transitions Initial state Fall 2006 Accept or Reject w Costas Busch - RPI 4 Consider now all strings of lengthn
T M (n) = maximum time required to decide any string of length n Fall 2006 Costas Busch - RPI 5 TIME T M (n) 1
2 3 4 n STRING LENGTH Max time to accept a string of length n
Fall 2006 Costas Busch - RPI 6 Time Complexity Class:TIME (T (n)) All Languages decidable by a deterministic Turing Machine in time O (T (n)) L1 L2 L3
Fall 2006 Costas Busch - RPI 7 n Example: L1 {a b : n 0} This can be decided in O (n) time TIME (n) n
L1 {a b : n 0} Fall 2006 Costas Busch - RPI 8 Other example problems in the same class TIME (n) n L1 {a b : n 0} n
{ab aba : n,k 0} n {b : n is even} n {b : n 3k } Fall 2006 Costas Busch - RPI 9 Examples in class:
2 TIME (n ) n n {a b : n 0} {wwR : w {a,b }} {ww : w {a,b }} Fall 2006 Costas Busch - RPI
10 Examples in class: 3 TIME (n ) CYK algorithm L2 {G,w : w is generatedby context - free grammarG } Matrix multiplication L3 { M1, M2, M3 : n n matrices
andM1 M2 M3 } Fall 2006 Costas Busch - RPI 11 Polynomial time algorithms:TIME k (n ) constant k 0
Represents tractable algorithms: for small k we can decide the result fast Fall 2006 Costas Busch - RPI 12 It can be shown: TIME (nk 1) TIME (nk ) TIME (nk 1) k
TIME (n ) Fall 2006 Costas Busch - RPI 13 The Time Complexity Class P k P TIME (n ) k 0
Represents: polynomial time algorithms tractable problems Fall 2006 Costas Busch - RPI 14 Class P n
{a b } n n {a b } {ww} CYK-algorithm Matrix multiplication Fall 2006
Costas Busch - RPI 15 nk Exponential time algorithms: TIME (2 ) Represent intractable algorithms: Some problem instances may take centuries to solve Fall 2006 Costas Busch - RPI
16 Example: the Hamiltonian Path Problem s t Question: is there a Hamiltonian path from s to t? Fall 2006 Costas Busch - RPI
17 s t YES! Fall 2006 Costas Busch - RPI 18 A solution: search exhaustively all paths
L = {: there is a Hamiltonian path in G from s to t} nk L TIME (n!) TIME (2 ) Exponential time Intractable problem Fall 2006 Costas Busch - RPI 19
The clique problem Does there exist a clique of size 5? Fall 2006 Costas Busch - RPI 20 The clique problem Does there exist a clique of size 5? Fall 2006 Costas Busch - RPI
21 Example: The Satisfiability Problem Boolean expressions in Conjunctive Normal Form: t1 t2 t3 tk clauses ti x1 x2 x3 x p Variables Question: is the expression satisfiable? Fall 2006 Costas Busch - RPI
22 Example: Satisfiable: ( x1 x2 ) ( x1 x3 ) x1 0, x2 1, x3 1 ( x1 x2 ) ( x1 x3 ) 1 Fall 2006 Costas Busch - RPI
23 Example: ( x1 x2 ) x1 x2 Not satisfiable Fall 2006 Costas Busch - RPI 24
L {w : expression w is satisfiable} nk L TIME (2 ) exponential Algorithm: search exhaustively all the possible binary values of the variables Fall 2006 Costas Busch - RPI 25 Non-Determinism
Language class: NTIME (T (n)) L1 L2 L3 A Non-Deterministic Turing Machine decides each string of length n in time O (T (n)) Fall 2006 Costas Busch - RPI
26 Non-Deterministic Polynomial time algorithms: k L NTIME ( n ) Fall 2006 Costas Busch - RPI 27 The class
NP k NP NTIME (n ) k 0 Non-Deterministic Polynomial time Fall 2006 Costas Busch - RPI 28
Example: The satisfiability problem L {w : expression w is satisfiable} Non-Deterministic algorithm: Guess an assignment of the variables Check if this is a satisfying assignment Fall 2006 Costas Busch - RPI 29 L {w : expression w is satisfiable}
Time for n variables: Guess an assignment of the variablesO (n) Check if this is a satisfying assignment O (n) Total time: O (n) Fall 2006 Costas Busch - RPI 30 L {w : expression w is satisfiable} L NP
The satisfiability problem is an NP - Problem Fall 2006 Costas Busch - RPI 31 Observation: P NP Deterministic Polynomial
Fall 2006 Non-Deterministic Polynomial Costas Busch - RPI 32 Open Problem: P NP ? WE DO NOT KNOW THE ANSWER
Fall 2006 Costas Busch - RPI 33 Open Problem: P NP ? Example: Does the Satisfiability problem have a polynomial time deterministic algorithm? WE DO NOT KNOW THE ANSWER
Fall 2006 Costas Busch - RPI 34