Deprecated: strlen(): Passing null to parameter #1 ($string) of type string is deprecated in /home/clients/b010bcc84441ff7c5adbaf4e922effaa/web/mom/module/pub/view-inc.php on line 105
Repository | Book | Chapter
Projection complete graph problems corresponding to a Branching-program-based characterization of the complexity classes nc1 ,land nl
pp. 283-292
Abstract
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
Published in:
Skordev Dimiter G (1987) Mathematical logic and its applications. Dordrecht, Springer.
Pages: 283-292
Deprecated: DateTime::createFromFormat(): Passing null to parameter #2 ($datetime) of type string is deprecated in /home/clients/b010bcc84441ff7c5adbaf4e922effaa/web/mom/module/pub/view-inc.php on line 496
DOI: 10.1007/978-1-4613-0897-3_20
Full citation:
Meinel Christoph (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, 283–292.