Klaus Reinhardt
und
Eric Allender
Wir zeigen, da\3 bei nichtuniformer Komplexität,
d.h. wenn für jede Eingabelänge ein Advice-string polynomieller
Länge zur Verfügung steht,
nichtdeterministische, logarithmisch platzbeschränkte
Berechnungen eindeutig gemacht werden können, d.h.
es kann nur einen akzeptierenden Pfad geben.
Gleiches gilt auch, wenn zusätzlich (bei polynomieller Zeitbeschränkung)
ein Keller zur Verfügung steht,
d.h. LogCFL/poly = UAuxPDA( 
)/poly.
In [Wig94, GW96] beobachtete Wigderson bereits Graphen, in welchen die kürzeste Distanz zwischen jedem Paar von Knoten eindeutig ist. Wir bezeichnen diese Graphen als min-unique. Durch die Technik des Isolations Lemmas aus [MVV87] kann mit Hilfe eines Advice strings ein Graph in eine Menge von Graphen umgewandelt werden, in der zumindest einer min-unique ist.
Eine Erweiterung der Zähltechnik aus [Imm88, Sze88], die wir
die Doppelzähltechnik nennen, weil sie in der k-ten Stufe
nicht nur die Anzahl Knoten mit Distanz 
, sondern auch die
Summe dieser Distanzen zählt, ermöglicht es
bereits gefundene Knoten auf eindeutige Weise wiederzufinden
und somit auf einem eindeutigen Pfad zu entscheiden, ob ein Graph
min-unique ist, und in diesem Fall die Erreichbarkeit im Graph zu entscheiden.