Projection complete graph problems corresponding to a Branching-program-based characterization of the complexity classes nc1 ,land nl

Christoph Meinel

pp. 283-292

in: Dimiter G. Skordev (ed), Mathematical logic and its applications, Berlin, Springer, 1987

Abstract

The p-projection completeness of some restricted graph accessibility problems for the (nonuniform) complexity classes NC ¹L and NL will be proved by means of branching-program-based characterizations of these classes. A simulation result concerning polynomial-size, bounded-width disjunctive branching programs and polynomial-size, bounded-width usual ones yields that NC ¹=L implies L=NL. Some consequences of these results for separating these classes are discussed.