Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept
Bernd Borchert, Antoni Lozano · 1996
This note connects two topics of Complexity Theory: The topic of succinct circuit representations initiated by Galperin and Wigderson [7], and the topic of leaf language classes initiated by Bovet et al. [5]. It will be shown for any language that its succinct version is polynomial-time many-one complete for the leaf language class determined by it. Keywords: computational complexity; leaf language classes; succinct representations; polynomial-time many-one completeness. 1 Introduction Consider the following well-known results concerning nondeterministic polynomial -time Turing machines, polynomial-time many-one reducibility p m , and Boolean circuits: ffl Let NP (PP, C=P, \\PhiP, 1-NP) be the class of languages for which there is a nondeterministic polynomial-time Turing machine which accepts if and only if there exists an accepting computation path (there is a majority of accepting computation paths, exactly half of the computation paths are accepting, there is an odd number of a...