In this paper, we combine two very useful algorithmic techniques (the inductive counting technique of [Imm88, Sze88] and the isolation lemma of [MVV87]) to give a simple proof that two fundamental concepts in complexity theory coincide in the context of nonuniform computation.
Unambiguous computation has been the focus of much attention over the past three decades. Unambiguous context-free languages form one of the most important subclasses of the class of context-free languages. The complexity class UP was first defined and studied by Valiant [Val76]; a necessary precondition for the existence of one-way functions is for P to be properly contained in UP [GS88]. Although UP is one of the most intensely-studied subclasses of NP, it is neither known nor widely-believed that UP contains any sets that are hard for NP under any interesting notion of reducibility. (Although Valiant and Vazirani showed that ``Unique.Satisfiability'' is hard for NP under probabilistic reductions [VV86], the language Unique.Satisfiability is not in UP unless NP = coNP.)
Nondeterministic and unambiguous space-bounded computation have also been the focus of much work in computer science. Nondeterministic logspace (NL) captures the complexity of many natural computational problems. The proof that NL is closed under complementation [Imm88, Sze88] answered the long-standing open question of whether the complement of every context-sensitive language is context-sensitive. It remains an open question if every context-sensitive language has an unambiguous grammar. The unambiguous version of NL, denoted UL, was first explicitly defined and studied in [BJLR92, AJ93]. A language A is in UL if and only if there is a nondeterministic logspace machine M accepting A such that, for every x, M has at most one accepting computation on input x.
Motivated in
part by the question of whether a space-bounded analog of the result
of [VV86] could be proved, Wigderson [Wig94, GW96]
proved the inclusion NL/poly 
L/poly.
This is a weaker statement than NL L, which is
still not known to hold. 
L is the class of languages A
for which there is a nondeterministic logspace bounded machine M
such that 
if and only M has an odd number of accepting
computation paths on input x. Given any complexity class 
,
/poly is the class of languages A for which there exists a
sequence of ``advice strings'' 
and
a language 
such
that if and only if 
. Classes of the
form provide a simple link between (nonuniform) circuit
complexity classes, and machine-based complexity classes (such
as P, NP, NL, L, etc.) that have natural characterizations
in terms of uniform circuit families.
(It is worth emphasizing that, in showing the equality UL/poly = NL/poly,
we must show that for every B in NL/poly, there is a nondeterministic
logspace machine M that never has more than one accepting path on any input, and
there is an advice sequence 
such that 
accepts if and only 
. This is stronger than merely saying
that there is an advice sequence and a nondeterministic logspace
machine such that never has more than one accepting
path, and it accepts if and only if .)
In the proof of the main result of [Wig94, GW96], Wigderson observed that a simple modification of his construction produces graphs in which the shortest distance between every pair of nodes is achieved by a unique path. We will refer to such graphs in the following as min-unique graphs. Wigderson wrote: ``We see no application of this observation.'' The proof of our main result is just such an application.