FORMAL LANGUAGES, AUTOMATA AND COMPUTABILITY15-453Read sections 7.1 – 7.3 of the book for next timeTIME COMPLEXITY OF ALGORITHMS(Chapter 7 in the textbook)COMPLEXITY THEORYStudies what can and can’t be computed under limited resources such as time, space, etc.Today: Time complexityMEASURING TIME COMPLEXITYWe measure time complexity by counting the elementary steps required for a machine to haltConsider the language A = { 0k1k| k ≥≥≥≥ 0 }1. Scan across the tape and reject if the string is not of the form 0m1n2. Repeat the following if both 0s and 1s remain on the tape:Scan across the tape, crossing off a single 0 and a single 13. If 0s remain after all 1s have been crossed off, or vice-versa, reject. Otherwise accept.2k2k22k•The number of steps that an algorithm uses on a particular input may depend on several parameters.•For instance, if the input is a graph, then the number of steps may depend on the number of nodes, the number of edges, et cetera.•For simplicity, we compute the running time purely as a function of the length of the input string and don’t consider any other parameters.Let M be a TM that halts on all inputs.Assume we compute the running time purely as a function of the length of the input string.Definition: The running time or time-complexityfunction of M is the function f : N →→→→ N such that f(n) is the maximum number of steps that M uses on any input of length n.ASYMPTOTIC ANALYSIS5n3+ 2n2+ 22n + 6 = O(n3)Big-O notation has been discussed in previous classes. We will briefly review it.Let f and g be two functions f, g : N →→→→ R+.We say that f(n) = O(g(n)) if positive integers c and n0exist so that for every integer n ≥≥≥≥ n0f(n) ≤≤≤≤ cg(n)When f(n) = O(g(n)), we say that g(n) is an asymptotic upper bound for f(n)BIG-O5n3+ 2n2+ 22n + 6 = O(n3)If c = 6 and n0= 10, then 5n3+ 2n2+ 22n + 6 ≤≤≤≤ cn33n log2n + 5n log2log2 n2n4.1+ 200283n4+ 2n log10n78= O(n4.1)= O(n log2n)= O(n log10n)log10 n = log2 n / log2 10O(n log2n) = O(n log10n) = O(n log n)Definition: TIME(t(n)) is the set of languages decidable in O(t(n)) time by a Turing Machine.{ 0k1k| k ≥≥≥≥ 0 } ∈∈∈∈ TIME(n2)A = { 0k1k| k ≥≥≥≥ 0 } ∈∈∈∈ TIME(n log n)Cross off every other 0 and every other 1. If the # of 0s and 1s left on the tape is odd, reject.00000000000001111111111111x0x0x0x0x0x0xx1x1x1x1x1x1xxxx0xxx0xxx0xxxx1xxx1xxx1xxxxxxxx0xxxxxxxxxxxx1xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxWe can prove that a (single-tape) TM can’t decide A faster than O(n log n).A = { 0k1k| k ≥≥≥≥ 0 }Can A = { 0k1k| k ≥≥≥≥ 0 } be decided in time O(n) with a two-tape TM?• Scan all 0s and copy them to the second tape.• Scan all 1s, crossing off a 0 from the second tape for each 1.Different models of computation yield different running times for the same language!Theorem.Let t(n) be a function such that t(n) ≥≥≥≥ n. Then every t(n)-time multi-tape TM has an equivalent O(t(n)2) single-tape TM.P = TIME(nk)∪∪∪∪k ∈∈∈∈ NPolynomial TimeNON-DETERMINISTIC TURING MACHINES AND NP0 → 0, Rread write move → , Rqacceptqreject0 → 0, R → , R0 → 0, RDETERMINISTIC TMsNON-NON-DETERMINISTIC TMs…are just like standard TMs, except:1. The machine may proceed according to several possibilities.2. The machine accepts a string if there exists a path from start configuration to an accepting configuration.DeterministicComputationNon-DeterministicComputationaccept or reject acceptrejectDefinition: A Non-Deterministic TM is a 7-tuple T = (Q, Σ, Γ, δδδδ, q0, qaccept, qreject), where: Q is a finite set of statesΓ is the tape alphabet, where  ∈∈∈∈ Γ and Σ ⊆⊆⊆⊆ Γq0∈∈∈∈ Q is the start stateΣ is the input alphabet, where  ∉∉∉∉ Σδδδδ : Q ×××× Γ → Pow(Q ×××× Γ ×××× {L,R})qaccept∈∈∈∈ Q is the accept stateqreject∈∈∈∈ Q is the reject state, and qreject≠≠≠≠ qacceptDeterministicComputationNon-DeterministicComputationaccept or reject acceptrejectthe set of languagesdecided by a O(t(n))-time non-deterministic Turing machine.Definition: NTIME(t(n)) isTIME(t(n)) ⊆⊆⊆⊆ NTIME(t(n))BOOLEAN FORMULAS(¬¬¬¬x ∧∧∧∧ y) ∨∨∨∨ zφφφφ =logical operationsvariablesparenthesesA satisfying assignment is a setting of the variables that makes the formula true.x = 1, y = 1, z = 1 is a satisfying assignment for φφφφBOOLEAN FORMULASx = 0, y = 0, z = 1 is a satisfying assignment for:¬¬¬¬(x ∨∨∨∨ y) ∧∧∧∧ (z ∧∧∧∧ ¬¬¬¬x)0 0 1 001 11Definition: SAT is the language consisting of all satisfiable boolean formulas.SAT = { φφφφ | φφφφ is a satisfiable boolean formula }A boolean formula is satisfiable if there exists a satisfying assignment for it.¬¬¬¬(x ∨∨∨∨ y) ∧∧∧∧ xa ∧∧∧∧ b ∧∧∧∧ c ∧∧∧∧ ¬¬¬¬dYESNO•A literal is a variable or the negation of a var.• Example: The variable x is a literal, andits negation, ¬¬¬¬x, is a literal.•A clause is a disjunction (an OR) of literals.• Example: (x ∨∨∨∨ y ∨∨∨∨ ¬¬¬¬z) is a clause.Conjunctive Normal Form (CNF)•A formula is in Conjunctive Normal Form (CNF)if it is a conjunction (an AND) of clauses.• Example: (x ∨∨∨∨ ¬¬¬¬ z) ∧∧∧∧ (y ∨∨∨∨ z) is in CNF.•A CNF formula is a conjunction of disjunctions of literals.Definition: A CNF formula is a 3CNF-formula iff each clause has exactly 3 literals.(x1∨∨∨∨ ¬¬¬¬x2∨∨∨∨ x3) ∧∧∧∧ (x4∨∨∨∨ x2∨∨∨∨ x5) ∧∧∧∧ ... ∧∧∧∧ (x3∨∨∨∨ ¬¬¬¬x2∨∨∨∨ ¬¬¬¬x1)clauses•A literal is a variable or the negation of a var.•A clause is a disjunction (an OR) of literals.•A formula is in Conjunctive Normal Form (CNF)if it is a conjunction (an AND) of clauses.•A CNF formula is a conjunction of disjunctions of literals.Definition: A CNF formula is a 3CNF-formula iff each clause has exactly 3 literals.(x1∨∨∨∨ ¬¬¬¬x2∨∨∨∨ x3) ∧∧∧∧ (x4∨∨∨∨ x2∨∨∨∨ x5) ∧∧∧∧ ... ∧∧∧∧ (x3∨∨∨∨ ¬¬¬¬x2∨∨∨∨ ¬¬¬¬x1)clauses(x1∨∨∨∨ ¬¬¬¬x2∨∨∨∨ x1)(x3∨∨∨∨ x1) ∧∧∧∧ (x3∨∨∨∨ ¬¬¬¬x2∨∨∨∨ ¬¬¬¬x1)(x1∨∨∨∨ x2∨∨∨∨ x3) ∧∧∧∧ (¬¬¬¬x4∨∨∨∨ x2∨∨∨∨ x1) ∨∨∨∨ (x3∨∨∨∨ x1∨∨∨∨