[ITOC-ch9] INTRACTABILITY

[ITOC-ch9] INTRACTABILITY

intractable

  • Problems that are solvable in principle, but the solutions require so much time or space that they can’t be used in practice.

9.1 HIERARCHY THEOREMS

giving a Turing machine more time or more space should increase the class of problems that it can solve.


space constructible

  • Example: All commonly occurring functions that are at least $ O(log n) $ are space constructible, including the functions $ log_2 n $ , $ n log_2 n $, and $ n^2 $ .

Space hierarchy theorem


COROLLARY 9.4

  • For any two functions $ f_1 , f_2 : N \longrightarrow N $, where $ f_1 (n) $ is $ o(f_2 (n)) $ and $ f_2 $ is space constructible

    $ SPACE(f_1 (n)) \subsetneq SPACE(f_2 (n)) $

COROLLARY 9.5

  • For any two real numbers $ 0 ≤ \epsilon_1 < \epsilon_2 $ , $ SPACE(n^{\epsilon_1} ) \subsetneq SPACE(n^{\epsilon_2} ) $.

COROLLARY 9.6

  • $ NL \subsetneq PSPACE $.
  • $ TQBF \in PSPACE$-complete, so $ TQBF \notin NL $

COROLLARY 9.7

  • $ PSPACE \subsetneq EXPSPACE $
  • establishes the existence of decidable problems that are intractable.

time constructible

  • Example: All commonly occurring functions that are at least $ n log n $ are time constructible, including the functions $ n log n $, $n \sqrt n $, $ n^2 $ , and $ 2^n $

Time hierarchy theorem


COROLLARY 9.11

  • For any two functions $t_1 , t_2 : N \longrightarrow N $ , where $ t_1 (n) $ is $ o(t_2 (n)/ logt_2 (n)) $ and $ t_2 $ is time constructible,

    $ TIME(t_1 (n)) \subsetneq TIME(t_2 (n)) $

COROLLARY 9.12

  • For any two real numbers $ 1 ≤ \epsilon_1 < \epsilon_2 $ , $ TIME(n^{\epsilon_1} ) \subsetneq TIME(n^{\epsilon_2} ) $

COROLLARY 9.13

  • $ P \subsetneq EXPTIME $

EXPONENTIAL SPACE COMPLETENESS

demonstrate that a specific language intractable:

  • TM can decide more languages in EXPSPACE than it can in PSPACE
  • show that the language is complete for EXPSPACE

EXPSPACE-complete


$ EQ_{REX↑} = \{ < Q, R > | \ Q \ and \ R \ are \ equivalent \ regular \ expressions \ with \ exponentiation\}. $

Proof

  • $ EQ_{REX↑} \in EXPSPACE $
    • Construct TM to decide $ EQ_{REX \uparrow}$
    • Convert Exp RE into Usual RE : $ 2^l $ length of EXP RE, at most $ n2^n $ length
    • Convert RE into NFA : increase $ O(n) $ space
    • Determine two NFA are equivalent or not : use $ O(n^2) $ space for deterministic TM on input n
    • Totally $ O(n22{2n}) $ space, therefore $ EXPSPACE $
  • $ EQ_{REX↑} \in EXPSPACE $-hard
    • The reduction maps an input $ w $ to a pair of RE, $R_1 $ and $ R_2 $, $ R_1 = R_2$ iff $ M $ accept $ w $
    • Recall Computation History: $ \# - C_1 - \#\#-C_2-\#…\#-C_l-\# $
    • $ R_1 = \Delta^{*} $ generates all strings over the alphabet consisting of symbols that may appear in computation histories.
    • $ R_2 = R_{ bad-start} ∪ R_{bad-window} ∪ R_{bad-reject} $ generates all strings that are not rejecting computation histories.
      • $ R_{bad-start} = S_0 ∪ S_1 ∪ · · · ∪ S_n ∪ S_b ∪ S_\# $
      • $ R_{bad-reject} = \Delta^∗_{−q_{reject}} $
      • $ R_{bad-window} = \bigcup_{bad(abc,def)} \Delta^{ * } abc \Delta^{2 ^ {(n^k)-2}} def \Delta^{ * } $
    • use repetition for exponent like $ \Delta{2{(n^k)-2}} $, length is $ 2 ^ {(n^k)} $, total length in binary is $ O(n^k) $ therefore polynomial time reducible.