[ITOC-ch7] TIME COMPLEXITY

[ITOC-ch7] TIME COMPLEXITY


7.1 MEASURING COMPLEXITY

BIG-O AND SMALL-O NOTATION

$ f(n) = O(g(n)) \ \Longleftrightarrow f(n) \ \le cg(n) $

$ f(n) = o(g(n)) \ \Longleftrightarrow f(n) \ \lt cg(n) $

polynomial bounds: with the form $ n^c $

exponential bounds: with the form $ 2^{ ( n^{\delta} ) } $


Time complexity

  • M is deterministic
  • f(n) is the maximum number of steps that M uses on any input of length n.

ANALYZING ALGORITHMS

TIME(t(n))

  • collection of languages that are decidable by a TM

nondeterministic Time complexity

  • N is nondeterministic
  • f(n) is the maximum number of steps that N uses on any branch of its computation on any input of length n

NTIME(t(n))

  • collection of languages that are decidable by a NTM

COMPLEXITY RELATIONSHIPS AMONG MODELS

computational model can affect the time complexity of languages

Theorem 7.8

  • Let $ t(n) $ be a function, where $ t(n) ≥ n $. Then every $ t(n) $ time multitape Turing machine has an equivalent $ O(t^2 (n)) $ time single-tape Turing machine
  • at most polynomial difference

Theorem 7.11

  • Let $ t(n) $ be a function, where $ t(n) ≥ n $. Then every $ t(n) $ time nondeterministic single-tape Turing machine has an equivalent $ 2^{O(t(n))} $ time deterministic single-tape Turing machine.
  • at most exponential difference

7.2 THE CLASS P

POLYNOMIAL TIME

polynomially equivalent

  • one of them can simulate another with only a polynomial increase in running time
  • All reasonable deterministic computational models are polynomially equivalent.

class P


Examples

  • $ PATH = \{ <G, s, t> | \ G \ is \ a \ directed \ graph \ that \ has \ a \ directed \ path \ from \ s \ to \ t\} $
  • $ RELPRIME = \{<x, y>| \ x \ and \ y \ are \ relatively \ prime\} $
  • Every context-free language is a member of P.

7.3 THE CLASS NP

class NP


Another equivalent definition

  • A verifier for a language A is an algorithm V , where
    $ A = \{w| \ V \ accepts \ <w, c> \ for \ some \ string \ c\} $
  • certificate: additional information $ c $ the verifier use


Proof of equivalence

Theorem 7.20

  • A language have polynomial verifiers iff it is decided by some nondeterministic polynomial time Turing machine.

Proof

  1. Assume that A is verified by a polynomial time TM $ V $ and construct $ N $
    • N nondeterministically select string c and run V for the verification
  2. Assume that A is decided by a polynomial time NTM $ N $ and construct $ V $
    • V treat each symbol of c as a description of the nondeterministic choice

Examples

  • $ HAMPATH = \{<G, s, t>| \ G \ is \ a \ directed \ graph \ with \ a \ Hamiltonian \ path \ from \ s \ to \ t\} $
  • $ COMPOSITES = \{x| \ x = pq, \ for \ integers \ p, q > 1 \} $
  • $ CLIQUE = \{<G, k>| \ G \ is \ an \ undirected \ graph \ with \ a \ k-clique \} $
  • $ SUBSET-SUM = \{<S, t>| \ S = \{x_1 , . . . , x_k \}, and \ for \ some \ \{y_1 , . . . , y_l \} ⊆ \{x_1 , . . . , x_k \}, \ we \ have \ Σy_i = t\} $

co-NP

  • languages that are complements of languages in NP
  • Verifying that something is not present seems to be more difficult than verifying that it is present.

THE P VERSUS NP QUESTION

$ P \subset NP $ or $ P = NP $


7.4 NP-COMPLETENESS

POLYNOMIAL TIME REDUCIBILITY

  • define a version of reducibility that takes the efficiency of computation into account

  • the reduction function is polynomial time computable

  • $ A ≤_P B $ than A is no harder than B


DEFINITION OF NP-COMPLETENESS

Theorem 7.35

  • If $ B $ is NP-complete and $ B ∈ P $, then $ P = NP $.

Theorem 7.36

  • If $ B $ is NP-complete and $ B ≤_P C $ for $ C $ in $ NP $, then $ C $ is NP-complete.

THE COOK—LEVIN THEOREM

$ SAT $ is NP-complete.

Idea

  • By DEF: show that every language $ A $ in NP is polynomial time reducible to SAT
  • Reduction function: takes a string w and produces a Boolean formula φ that simulates the NP machine for A on input w, while w is in A iff φ is satisfiable
  • the problem of determining whether N accepts w is equivalent to the problem of determining whether an accepting tableau for N on w exists.
  • 将每个configuration里的每个symbol都设为一个变量, 按照A accept w的过程来模拟布尔表达式, 构造的表达式只保证符合TM的计算过程(对应的表格是合法的), 只有当accept的时候表达式才有真的赋值

Proof

  • variable: For each $ i $ and $ j $ between 1 and $ n^k $ and for each $ s $ in $ C = Q ∪ Γ ∪ \{ \# \} $, we have a variable, $ x_{i,j,s} $, If $ x_{i,j,s} $ takes on the value 1, it means that $ cell [i, j] $ in the tableau contains an s

  • formula φ: $ φ_{cell} ∧ φ_{start} ∧ φ_{move} ∧ φ_{accept} $

    • $ φ_{cell} ​$: ensure that there must have exactly one variable on for every cell (tableau is valid)

    • $ φ_{start} $: ensure that the first row of the table is the starting configuration

    • $ φ_{accept} $:ensure that an accepting configuration occurs in the tableau

    • $ φ_{move} $: ensure that each row’s configuration legally follows the preceding row’s configuration according to N ’s rules.

      • Ensure each 2 × 3 window of cells is legal

  • complexity of the reduction: $ O(n^{2k} ) $


7.5 ADDITIONAL NP-COMPLETE PROBLEMS

(几乎都是从3SAT reduce 来的…感觉比CLRS难哭唧唧感觉还是CLRS讲的懂一点x)

CLIQUE

VERTEX-COVER

HAMPATH

UHAMPATH

SUBSET-SUM