next up previous
Next: Discussion and Open Problems Up: Making Nondeterminism Unambiguous Previous: Nondeterministic Logspace


LogCFL is the class of problems logspace-reducible to a context-free language. Two important and useful characterizations of this class are summarized in the following proposition. (SAC tex2html_wrap_inline1046 and AuxPDA tex2html_wrap_inline1048 are defined in the following paragraphs.)


An Auxiliary Pushdown Automaton (AuxPDA) is a nondeterministic Turing machine with a read-only input tape, a space-bounded worktape, and a pushdown store that is not subject to the space-bound. The class of languages accepted by Auxiliary Pushdown Automata in space s(n) and time t(n) is denoted by AuxPDA(s(n),t(n)). If an AuxPDA satisfies the property that, on every input x, there is at most one accepting computation, then the AuxPDA is said to be unambiguous. This gives rise to the class UAuxPDA(s(n),t(n)).

SAC tex2html_wrap_inline1046 is the class of languages accepted by logspace-uniform semi-unbounded circuits of depth tex2html_wrap_inline1066 ; a circuit family is semi-unbounded if the AND gates have fan-in 2 and the OR gates have unbounded fan-in.

Not long after NL was shown to be closed under complementation [Imm88, Sze88], LogCFL was also shown to be closed under complementation in a proof that also used the inductive counting technique ([BCD tex2html_wrap_inline1780 89]). A similar history followed a few years later: not long after it was shown that NL is contained in tex2html_wrap_inline550 L/poly [Wig94, GW96], the isolation lemma was again used to show that LogCFL is contained in tex2html_wrap_inline550 SAC tex2html_wrap_inline1046 /poly [Gál95, GW96]. (As is noted in [GW96], this was independently shown by H. Venkateswaran.)

In this section, we show that the same techniques that were used in Section gif can be used to prove an analogous result about LogCFL. (In fact, it would also be possible to derive the result of Section gif from a modification of the proof of this section. Since some readers may be more interested in NL than LogCFL, we have chosen to present a direct proof of NL/poly = UL/poly.) The first step is to state the analog to Lemma gif. Before we can do that, we need some definitions.

A weighted circuit is a semiunbounded circuit together with a weighting function that assigns a nonnegative integer weight to each wire connecting any two gates in the circuit.

Let C be a weighted circuit, and let g be a gate of C. A certificate for g(x) = 1 (in C) is a list of gates, corresponding to a depth-first search of the subcircuit of C rooted at g. The weight of a certificate is the sum of the weights of the edges traversed in the depth-first search. This informal definition is made precise by the following inductive definition. (It should be noted that this definition differs in some unimportant ways from the definition given in [Gál95, GW96].)

Note that if C has logarithmic depth d, then any certificate has length bounded by a polynomial in n and has weight bounded by tex2html_wrap_inline1168 times the maximum weight of any edge. Every gate that evaluates to 1 on input x has a certificate, and no gate that evaluates to 0 has a certificate.

We will say that a weighted circuit C is min-unique on input x if, for every gate g that evaluates to 1 on input x, the minimal-weight certificate for g(x) = 1 is unique.


Lemma gif is in some sense implicit in [Gál95, GW96]. We include a proof for completeness.

Proof: Let A be in LogCFL, and let C be the semiunbounded circuit of size tex2html_wrap_inline1214 and depth tex2html_wrap_inline1216 recognizing A on inputs of length n.

As in [Gál95, GW96], a modified application of the isolation lemma technique of [MVV87] shows that, for each input x, if each wire in C is assigned a weight in the range tex2html_wrap_inline1226 uniformly and independently at random, then with probability at least tex2html_wrap_inline650 , C is min-unique on input x. (Sketch: The probability that there is more than one minimum weight certificate for g(x) = 1 is bounded by the sum, over all wires e, of the probability of the event BAD(e,g) ::= ``e occurs in one minimum-weight certificate for g(x) = 1 and not in another''. Given any weight assignment w' to the edges in C other than e, there is at most one value z with the property that, if the weight of e is set to be z, then BAD(e,g) occurs. Thus the probability that there are two minimum-weight certificates for any gate in C is bounded by tex2html_wrap_inline1260 tex2html_wrap_inline690 tex2html_wrap_inline1264 = tex2html_wrap_inline1266 .)

Now consider sequences tex2html_wrap_inline1268 consisting of n weight functions tex2html_wrap_inline1272 , where each weight function assigns a weight in the range tex2html_wrap_inline1226 to each edge of C. (There are tex2html_wrap_inline1278 such sequences possible for each n.) There must exist a string tex2html_wrap_inline1268 such that, for each input x of length n, there is some tex2html_wrap_inline1288 such that the weighted circuit tex2html_wrap_inline1290 that results by applying weight function tex2html_wrap_inline1120 to C is min-unique on input x. (Sketch of proof: Let us call a sequence tex2html_wrap_inline1268 ``bad for x'' if none of the circuits tex2html_wrap_inline1290 in the sequence is min-unique on input x. For each x, the probability that a randomly-chosen tex2html_wrap_inline1268 is bad is bounded by (probability that tex2html_wrap_inline1290 is not min-unique) tex2html_wrap_inline1312 tex2html_wrap_inline1314 . Thus the total number of sequences that are bad for some x is at most tex2html_wrap_inline1318 . Thus there is some sequence tex2html_wrap_inline1268 that is not bad.)

The desired advice sequence tex2html_wrap_inline1322 is formed by taking a good sequence tex2html_wrap_inline1324 and letting tex2html_wrap_inline1290 be the result of applying weight function tex2html_wrap_inline1120 to C.


Proof: Let A be a language in LogCFL. Let x be a string of length n, and let tex2html_wrap_inline1342 be the advice sequence guaranteed by Lemma gif.

We show that there is an unambiguous auxiliary pushdown automaton M that runs in polynomial time and uses logarithmic space on its worktape that, given a sequence of circuits as input, processes each circuit in turn, and has the following properties:

Our construction is similar in many respects to that of Section gif. Given a circuit C, let tex2html_wrap_inline832 denote the number of gates g that have a certificate for g(x)=1 of weight at most k, and let tex2html_wrap_inline834 be the sum, over all gates g having a certificate for g(x) = 1 of weight at most k, of the minimum-weight certificate of g. (Let W(g) denote the weight of the minimum-weight certificate of g(x) = 1, if such a certificate exists, and let this value be tex2html_wrap_inline1394 otherwise.)

A useful observation is that if all gates of C having certificates of weight at most k have unique minimal-weight certificates (and if the correct values of tex2html_wrap_inline832 and tex2html_wrap_inline834 are provided), then an unambiguous AuxPDA can, on input tex2html_wrap_inline1404 , compute the Boolean value of the predicate `` tex2html_wrap_inline1406 ''. This is achieved with the routine shown in Figure gif.

Figure: An unambiguous routine to calculate W(g) if tex2html_wrap_inline1446 and return tex2html_wrap_inline1394 otherwise.

To see that this routine truly is unambiguous if the preconditions are met, note the following:

Clearly, all gates at the input level have unique minimal-weight certificates (and the only gates g with W(g)= 0 are at the input level). Thus we can set tex2html_wrap_inline1474 (since each input bit and its negation are provided, along with the constant 1), and tex2html_wrap_inline1476 . A key part of the construction involves computing tex2html_wrap_inline832 and tex2html_wrap_inline834 from tex2html_wrap_inline1482 , at the same time checking that no gate has two minimal-weight certificates of weight k. Consider each gate g in turn. If g is an AND gate with inputs tex2html_wrap_inline1100 and tex2html_wrap_inline1102 and weights tex2html_wrap_inline1494 and tex2html_wrap_inline1496 connecting g to these inputs, then tex2html_wrap_inline1500 if and only if tex2html_wrap_inline1502 or ((W(g) > k-1) and ( tex2html_wrap_inline1506 )). If g is an OR gate, then it suffices to check, for each gate h that is connected to g by an edge of weight w, if tex2html_wrap_inline1502 or ((W(g) > k-1) and (W(h)+w=k)); if one such gate is found, then W(g) = k; if two such gates are found, then the circuit is not min-unique on input x. If no violations of this sort are found for any k, then C is min-unique on input x. The code shown in Figure gif formalizes these considerations.

Figure: Computing tex2html_wrap_inline832 and tex2html_wrap_inline834 .

Evaluating a given circuit tex2html_wrap_inline1290 is now expressed by the routine shown in Figure gif.

Figure: Evaluating a circuit.

Given the sequence tex2html_wrap_inline1342 , the routine processes each tex2html_wrap_inline1290 in turn. If tex2html_wrap_inline1290 is not is min-unique on input x, then one unique computation path of the routine returns the value BAD.CIRCUIT and goes on to process tex2html_wrap_inline1352 ; all other computation paths halt and reject. Otherwise, the routine has a unique accepting path if tex2html_wrap_inline1622 , and if this is not the case the routine halts with no accepting computation paths.


next up previous
Next: Discussion and Open Problems Up: Making Nondeterminism Unambiguous Previous: Nondeterministic Logspace

Klaus Reinhardt
Mon Apr 28 16:41:00 MST 1997