Succinct Representation, Leaf Languages, and Projection Reductions

In this article, the following results are shown: 1. For succinctly encoded problemss(A), completeness under polynomial time reductions is equivalent to completeness under projection reductions, an extremely weak reduction defined by a quantifier-free projective formula. 2. The succinct versions(Aof a computational problemAis complete under projection reductions for the class of problems characterizable with leaf languageA, but not complete undermonotoneprojections. 3. A strong conversion lemma: IfAis reducible toBin polylogarithmic time, then the succinct version ofAis monotone projection reducible to the succinct version ofB. This result strengthens previous results by Papadimitriou and Yannakakis, and Balcázar and Lozano. It allows iterated application for multiple succinct problems. 4. For all syntactic complexity classes there exist complete problems undermonotoneprojection reductions. This positively answers a question by Stewart for a large number of complexity classes.

Authors

• Helmut Veith

Keywords

No keywords are indexed for this paper.