计算机理论复杂度代写: CSC427 HW #9

计算理论 Theory of Computation

CSC427 Spring 2018, HW #9 (extra credit)

Mitsu Ogihara
Due date: Monday, April 30

  1. (10 points) Show that the polynomial-time mapping reducibility ≤pm is a transitive relation; that is, for all languages A, B, and C, A ≤pm B and B ≤pm C implies A ≤pm C.
  2. (10 points) Show that SAT cannot be polynomial-time mapping reducible to the empty set.
  3. (50 points) Define H = {⟨M,k⟩ | M is an NFA, k is an integer, and there is no NFA with at most k states that accepts the same language as H}. Show that SAT is mapping-reducible to H in the following manner:
    1. (a)  (40 points) Let φ = C1 ∧ ··· ∧ Cm be a 3CNF formula with some n variables and some m clauses. We can view each 0/1-sequence having length n as a truth- assignment to the variables of φ, where for each i, 1 ≤ i ≤ n, the i-th bit of the sequence represents the value given to the i-th variable of φ.
      1. (10points)Foreachi,1≤i≤m,letLi ={x|xisa0/1sequencehaving length n that represents a truth-assignment that fails to satisfy Ci}. Show that for each i, 1 ≤ i ≤ m, there exists an NFA with n + 1 states for Li.
      2. (10 points) Show that there is a DFA with n+2 states for L0 = {x | x is a 0/1 sequence whose length is not equal to n}.
      3. (5 points) Define L to be the union of L0, L1, · · · , Lm. Using the above two results, show that there is an NFA with at most (m + 1)(n + 1) + 1 states for L.
      4. (10 points) Show that φ is not satisfiable if and only if L = {0, 1}∗.
      5. (5 points) Show that there is a one-state NFA (actually DFA) for {0,1}∗.
    2. (b)  (10 points) Using the above observations, show that SAT is polynomial-time map- ping reducible to H.
  4. (30 points) Let G be a graph. An independent set of G is a set of nodes in G such that no two nodes in the set are joined by an edge. Define I = {⟨G,k⟩ | G has an independent set with k elements }. Show that I is NP-complete as follows:

    (a) (10 points) Show that I is NP.
    1

  1. (b)  (10 points) For a graph G, define G to the complementary graph of G; that is, two nodes u and v are joined by an edge in G if and only if u and v are not joined by an edge in G. Show that for all positive integers k, G has a clique with k elements if and only if G has an independent set with k elements.
  2. (c)  (10 points) Using the above result, show that CLIQUE is polynomial-time map- ping reducible to I.

2

Related Posts