Leaf languages are a beautiful way to uniformly define many complexity classes. Most complexity classes are usually specified by a model of computation (e.g., deterministic/randomized TM), and a resource bound (log time, poly space, etc.). However in the leaf language formulation, there is only one model of computation, and the class is specified by giving its leaf language.

The details are too long to explain, so I'll direct interested readers to either of these two surveys:

  1. Uniform characterizations of complexity classes by H Vollmer
  2. Leaf Language Classes by KW Wagner

Both surveys do a great job of explaining the formulation within the first few pages.

In Wagner's survey, he says "it turns out that practically every complexity class considered so far can be described by leaf languages."

My question relates to this statement. I know there are some classes for which we do not know a leaf language characterization, so this means either the classes don't necessarily have such a characterization, or we haven't found it.

Do we expect every complexity class (say between P and PSPACE) to have a leaf language characterization? (Let's restrict ourselves to "natural" complexity classes.) Is there any result of this sort in the literature?

(A related question that I'd be happy to know the answer to: Is there a (heuristic) method to come up with a leaf language for a given class?)

EDIT: Suresh points out that there is a short definition of leaf languages in the Wikipedia article. I'm copying it below.

Several complexity classes are typically defined in terms of a polynomial-time nondeterministic Turing machine, where each branch can either accept or reject, and the entire machine accepts or rejects as some function of the branches' conditions. For example, a non-deterministic Turing machine accepts if at least one branch accepts, and rejects only if all branches reject. A co-non-deterministic Turing machine, on the other hand, accepts only if all branches accept, and rejects if any branch rejects. Many classes can be defined in this fashion.

  • 1
    $\begingroup$ wikipedia has a fairly succinct defn of a leaf language: maybe you can adapt that into the question ? $\endgroup$ – Suresh Venkat Aug 30 '10 at 4:12
  • $\begingroup$ Thanks. I didn't know Wikipedia had an article on it. I've copied their definition at the end of my question. $\endgroup$ – Robin Kothari Aug 30 '10 at 4:36

Have a look at

Bernd Borchert, Riccardo Silvestri: A Characterization of the Leaf Language Classes. Inf. Process. Lett. 63(3): 153-158 (1997) (doi link here)

The authors characterize the leaf language classes as those which are (a) "countable", (b) are "downward" closed wrt polytime many-one reducibility, and (c) "join-closed" (i.e., disjoint union) wrt polytime many-one reducibility.

More formally, all the languages $L$ in a leaf language class have a bijection with the natural numbers, and the property that for every $C,D \in L$, if $E \leq^P_m C \sqcup D$ then $E \in L$ as well (the $\sqcup$ denotes disjoint union). Also, every "non-leaf language class" contains a language which fails to have one of these properties.

From these three conditions we can get many examples of classes which aren't leaf language classes. For example, the "countable" condition rules out advice classes like $P/poly$, and the "downward closed wrt polytime many-one reducibility" rules out fixed resource-bound classes like $SPACE[n]$. (Recall that the usual proof that $SPACE[n] \neq P$ uses the fact that $SPACE[n]$ is not closed under such reductions.)

  • 2
    $\begingroup$ Great. That's what I needed. (Any idea how to find such a characterization after knowing that it exists? Maybe even a heuristic, and not something that always works?) $\endgroup$ – Robin Kothari Aug 30 '10 at 15:57
  • 1
    $\begingroup$ In this case, my impression is that the authors built on known results of the form "all leaf languages have property X" and "no leaf language has property Y", and found a direct way to tie all these together by adding just the right conditions. $\endgroup$ – Ryan Williams Aug 30 '10 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.