Repository | Book | Chapter
(1987) Mathematical logic and its applications, Dordrecht, Springer.
Projection complete graph problems corresponding to a Branching-program-based characterization of the complexity classes nc1 ,land nl
Christoph Meinel
pp. 283-292
The p-projection completeness of some restricted graph accessibility problems for the (nonuniform) complexity classes NC 1L 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 1=L implies L=NL. Some consequences of these results for separating these classes are discussed.
Publication details
DOI: 10.1007/978-1-4613-0897-3_20
Full citation:
Meinel, C. (1987)., Projection complete graph problems corresponding to a Branching-program-based characterization of the complexity classes nc1 ,land nl, in D. G. Skordev (ed.), Mathematical logic and its applications, Dordrecht, Springer, pp. 283-292.
This document is unfortunately not available for download at the moment.