Bernd Borchert, Antoni Lozano

This note connects two topics of Complexity Theory: The

topic of succinct circuit representations initiated by

Galperin and Wigderson and the topic of leaf languages

initiated by Bovet, Crescenzi, and Silvestri. It will be

shown for any language that its succinct version is

more >>>

Till Tantau

Deciding whether a vertex in a graph is reachable from another

vertex has been studied intensively in complexity theory and is

well understood. For common types of graphs like directed graphs,

undirected graphs, dags or trees it takes a (possibly

nondeterministic) logspace machine to decide the reachability

problem, and ...
more >>>