[next] [prev] [prev-tail] [tail] [up]

5.6  P-Complete Problems

      The Nonterminal Symbols of Gx
      The Production Rules of Gx

In some cases it is of interest to study the limitations of some subclasses of P. The motivation might be theoretical, as in the case of the subclass NLOG of P, or practical, as in the case of the subclass U_NC of the problems in P that can be solved by efficient parallel programs (see Section 7.5). In such cases the notion of the "hardest" problems in P is significant.

Specifically, a problem K1 is said to be logspace reducible to a problem K2 if there exist logspace-bounded, deterministic Turing transducers Tf and Tg that for each instance I1 of K1 satisfy the following conditions.

  1.  Tf on input I1 gives an instance I2 of K2.
  2.  K1 has a solution S1 at I1 if and only if K2 has a solution S2 at I2, where S1 is the output of Tg on input S2.
A problem K is said to be a P-hard problem if every problem in P is logspace reducible to K. The problem is said to be P-complete if it is a P-hard problem in P.

By the definitions above, the P-complete problems are the hardest problems in P, and by Section 7.5 NLOG (_ U_NC (_ P . Consequently, NLOG contains a P-complete problem if and only if P = NLOG, and U_NC contains a P-complete problem if and only if P = U_NC. It is an open problem whether P equals NLOG or U_NC.

Theorem 5.6.1    The emptiness problem for context-free grammars is P-complete.

Proof     Consider any context-free grammar G =< N, S, R, S >. The emptiness of L(G) can be determined by the following algorithm.

Step 1
Mark each of the terminal symbols in S.
Step 2
Search R for a production rule A --> a, in which a consists only of marked symbols and A is unmarked. If such a production rule A --> a exists, then mark A and repeat the process.
Step 3
If the start symbol S is unmarked, then declare L(G) to be empty. Otherwise, declare L(G) to be nonempty.
The number of iterations of Step 2 is bounded above by the number of nonterminal symbols in N. Consequently, the algorithm requires polynomial time and the problem is in P.

To show that the emptiness problem for context-free grammars is P-hard, consider any problem K in P. Assume that M = <Q, S, G, d, q0, B, F> is a deterministic Turing machine that decides K in T(n) = O(nk) time and that Q /~\ (S U G U {¢, $}) = Ø. Let m denote the number of auxiliary work tapes of M, and let r denote the cardinality of d. Then K can be reduced to the emptiness problem for context-free grammars by a logspace-bounded, deterministic Turing transducer TK of the following form.

TK on input x outputs a context-free grammar Gx such that

  1.  L(Gx) = Ø if K has answer yes at x.
  2.  L(Gx) = {e} if K has answer no at x.
TK constructs the grammar Gx to describe the computation of M on input x.

 The Nonterminal Symbols of Gx

The nonterminal symbols of Gx represent the possible characteristics of the computation of M on input x. Specifically, Gx has the following nonterminal symbols (t is assumed to denote the value T(|x|)).

  1.  The start symbol S. S represents the possibility of having a nonaccepting computation of M on input x.
  2.  A nonterminal symbol Ai,t for each transition rule t of M and each 1 <= i <= t. Ai,t represents the possibility that the ith move of M on input x uses the transition rule t.
  3.  A nonterminal symbol Ai,0,j,X for each 0 <= i <= t, 1 <= j <= |x| + 3, and X in {¢, $} U S U Q. Ai,0,j,X represents the possibility of having X in the ith configuration of the computation at the jth location of the input description.
  4.  A nonterminal symbol Ai,r,j,X for each 0 <= i <= t, 1 <= r <= m, 1 <= j <= 2t + 1, and X in G U Q. Ai,r,j,X represents the possibility of having X in the ith configuration of the computation at the jth location of the rth auxiliary work tape description.
  5.  A nonterminal Bi,r,q,X for each 0 <= i <= t, 0 <= r <= m, q in Q, and X in S U G U {¢, $}. Bi,r,q,X represents the possibility that in the ith configuration the state is q and the symbol under the head of the rth tape is X.

 The Production Rules of Gx

The production rules of Gx describe how the characteristics of the computation of M on input x are determined. Specifically, the characteristic that is represented by a nonterminal symbol A holds for the computation if and only if A ==>* e in Gx. The production rules of Gx are as follows.

  1.  Production rules that determine the input segment in the initial configuration. 

              A0,0,1,c|  -->   e
         A0,0,2,q0  -->   e
A0,0,i+2,ithsymbolinx  -->   e    for1 <= i <= |x|
       A0,0,|x|+3,$  -->   e
  2.  Production rules that determine the segment of the rth auxiliary work tape in the initial configuration, 1 <= r <= m. 

       A0,r,j,B  -->   e    for1 <= j <= tandt+ 2 <= j <= 2t+ 1
A0,r,t+1,q0 -->   e
  3.  Production rules that determine the jth symbol for the rth tape in the ith configuration of the computation. 

     Ai,r,j,X  -->   Ai-1,r,j- 1,YAi-1,r,j,ZAi-1,r,j+1,WAi,t

    for each X, Y, Z, W, t, such that fr(Y, Z, W, t) = X. fr(Y, Z, W, t) is assumed to be a function that determines the replacement X of Z for the rth tape when Y is to the left of Z, W is to the right of Z, and t is the transition rule in use. The left "boundary symbols" Ai-1,0,-1,Y , . . . , Ai-1,m,-1,Y , Ai-1,0,|x|+4,W and the right ones Ai-1,1,2t+2,W , . . . , Ai-1,m,2t+2,W are assumed to equal the empty string e.

  4.  Production rules that determine whether the computation is nonaccepting. 

     S  -->   B     B      ... B
         i,0,q,a i,1,q,b1    i,m,q,bm

    for each 0 <= i <= t, a nonaccepting state q, and a, b1, . . . , bm such that d(q, a, b1, . . . , bm) = Ø (i.e., M has no next move).

  5.  Production rules that determine the transition rule to be used in the ith move of the computation, 1 <= i <= t. 

     Ai,t -->   Bi-1,0,q,aBi-1,1,q,b1 ... Bi- 1,m,q,bm

    for each transition rule t = (q, a, b1, . . . , bm, p, do, c1, d1, . . . , cm, dm) of the Turing machine M.

    Since M is deterministic, for a given i there exists at most one t such that Ai,t ==>* e.

  6.  Production rules that are used for determining the state of M and the symbols scanned by the heads of M in the ith configuration, 0 <= i <= t. 

       Bi,0,q,a  -->   Ai,0,j0,qAi,0,j0+1,a
 Bi,1,q,b1  -->   Ai,1,j1,qAi,1,j1+1,b1
          ...
Bi,m,q,bm   -->   Ai,m,jm,qAi,m,jm+1,bm

    for each 1 <= j0 <= |x| + 2, and 1 <= jr <= 2t with 1 <= r <= m. ***

Example 5.6.1    Let M be the deterministic Turing machine of Figure 5.3.3(a), x = ab, and assume the notations in Theorem 5.6.1.

The following production rules of Gx determine the input segment in the initial configuration of M on x. 

 A0,0,1,c  -->  e
A0,0,2,q0 -->  e
A0,0,3,a  -->  e
A0,0,4,b  -->  e
A0,0,5,$  -->  e

The production rules that determine the segment of the auxiliary work tape in the initial configuration have the following form. 

 B0,0,j,B  -->   e    1 <= j <= 4and6 <= j <= 9
B0,0,5,q0 -->   e

The following production rules determine the second configuration from the first. 

 A     |  -->          A    |A      A
A 1,0,1,c   -->   A    | A0,0,1,cA 0,0,2,q0A 1,t1
A 1,0,2,a   -->   A0,0,1,c A0,0,2,q0A 0,0,3,a A 1,t1
A 1,0,3,q0  -->   A0,0,2,q0 A0,0,3,aA 0,0,4,b A 1,t1
A 1,0,4,b   -->   A0,0,3,a A0,0,4,b  0,0,5,$ A 1,t1
A 1,0,5,$   -->    0,0,4,b A0,0,5,$A      A 1,t1
A 1,1,1,B   -->   A      A0,1,1,BA 0,1,2,B A 1,t1
A 1,1,2,B   -->   A0,1,1,B A0,1,2,BA 0,1,3,B A 1,t1
A 1,1,3,B   -->   A0,1,2,B A0,1,3,BA 0,1,4,B A 1,t1
A 1,1,4,B   -->   A0,1,3,B A0,1,4,BA 0,1,5,q0A 1,t1
A 1,1,5,a   -->   A0,1,4,B A0,1,5,q0A 0,1,6,B A 1,t1
A 1,1,6,q0  -->   A0,1,5,q0 A0,1,6,BA 0,1,7,B A 1,t1
A 1,1,7,B   -->   A0,1,6,B A0,1,7,BA 0,1,8,B A 1,t1
A 1,1,8,B   -->   A0,1,7,B A0,1,8,B  0,1,9,B A 1,t1
  1,1,9,B        0,1,8,B  0,1,9,B         1,t1

The production rule A1,t1 --> B0,0,q0,aB0,1,q0,B determines the transition rule used in the first move.

The following production rules determine the state of M and the symbols scanned by the heads of M, in the first configuration. 

  B       -->   A      A
B 0,0,q0,a -->   A 0,0,2,q0A0,0,3,a
  0,1,q0,B        0,1,5,q0 0,1,6,B

PICT

[next] [prev] [prev-tail] [front] [up]