Problems that are complete for complexity classes usually turn outto be complete under very restrictive types of reducibility. Althoughthis has frequently been observed informally, only very recently hasthere been work proving that this must sometimes be the case. Veithshows that any “succinctly-encoded problem” that is completeunder polynomial-time reductions is already complete underquantifier-free projections. Thus, for these problems, very powerfulreductions can be replaced by almost trivial reductions. (Independently,my co-authors and I have proven that a much smaller collapse holds evenwhen the succinctness condition is dropped [1].) Succinctly-encodedproblems have been studied by several authors, and this collapse is ofgeneral interest.

As an added benefit, Veith’s results strengthen connections betweensuccinct representations and the leaf-language approach to computationalcomplexity. Through careful definitions and deft manipulation of theformalism, he is able to answer questions left open by previous authors,especially concerning the existence of problems complete under monotoneprojections.

The presentation is quite clear. This work will beuseful for anyone working with restricted reducibilities (especiallyprojections) and for those studying leaf languages.