Languages and Finite Automata

Languages and Finite Automata

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

Recently Viewed Presentations

  •  Bulgarian policy for improving EE in buildings facts

    Bulgarian policy for improving EE in buildings facts

    Bulgarian policy for improving EE in buildings- facts by October 2009 CONTENTS Current status- Country EE profile Legal acts EE measures in residential and service sectors Concrete facts from EE audits in public sector buildings Overview Over the period 1997...
  • Impressionism 'All that is solid melts into air' (Marx and ...

    Impressionism 'All that is solid melts into air' (Marx and ...

    in Latin America "The Royal Academy of San Carlos in Mexico City, founded in 1785, was the first academy of art in America, and the only one established under colonial ruleā€¦. In Brazil, the Academia Imperial de Belas Artes was...
  • Energy Efficiency Product Database

    Energy Efficiency Product Database

    Public Portal. Through which assessors can view and make decisions on applications. ... It is a known fact that no significant market surveillance testing has been conducted on other regulated lamp types ( tungsten filament lamps and CFL's).( NRCS spends...
  • Early Expression of Autism Spectrum Disorders Kasia Chawarska,

    Early Expression of Autism Spectrum Disorders Kasia Chawarska,

    Title: No Slide Title Author: Patrick Lynch Last modified by: Kirsten Cartoski Created Date: 3/15/2010 7:13:09 AM Document presentation format: On-screen Show (4:3)
  • Stuart Little - Allamuchy Township School District

    Stuart Little - Allamuchy Township School District

    Stuart Little summarize. This story takes place in New York City in a house across the street from Central Park. The main characters are Stuart Little, who is a mouse, and his adoptive family the Little's, their son George, the...
  • Wellness is Worth It! How to Successfully Implement

    Wellness is Worth It! How to Successfully Implement

    Students in grades 9-12 must receive one half unit of physical education at some point from 9th through 12th grade, with no additional requirement for physical activity. State Physical Activity & Physical Education Standards. What is the student-to-teacher ratio for...
  • CDC Presentation

    CDC Presentation

    How is pneumonia spread? Most cases of pneumonia are spread person-to-person by coughing out of tiny droplets. Some pathogens can live in nose and throat without causing disease.
  • Review of qualitative Research AND PRINCIPLES of Qualitative

    Review of qualitative Research AND PRINCIPLES of Qualitative

    * Types of Qualitative Research Grounded theory Ethnography Phenomenology Field research * Strengths and Weaknesses Strengths Depth of understanding Flexibility Weaknesses Subjectivity Suggestive, not definitive Limited generalizability Mixed methodology is possible * Qualitative Research Terms ...