Geometric sets of low information content

Abstract

In this paper we study language classes defined by nonuniform families of hyperplanes and halfspaces. These are subclasses of P/poly. Upto many-one equivalence these classes are essentially the classes ELT₁ (and LT₁) of languages accepted by nonuniform families of polynomial size depth-1 circuits with a weighted exact threshold gate at the root (respectively, weighted threshold gate at the root). We investigate the consequences of intractable sets being reducible to sets in ELT₁ and LT₁. Using the polynomial-time algorithm for linear programming and ideas from the theory of convex polytopes we prove that every disjunctively self-reducible bd-cylinder that is many-one reducible to a set in ELT₁ or LT₁ is already in P. As a consequence we derive that if a complete set for any class K > ε { NP. Mod₁P. PP. C = P} many-one reduces to a set in ELT₁ or LT₁ then K > = P . For families of hyperplanes over finite fields, we prove that every Turing self-reducible set that is many-one reducible to a set defined by such a family is in P, and every word-decreasing self-reducible set that is many-one reducible to a set defined by such a family is in NP n co-NP. Furthermore, as an interesting connection, it turns out that several sparse and tally reduction classes are many-one reducible to ELT₁ or LT₁. Thus, our results concerning reductions to ELT₁ and LT₁ subsume the strongest existing collapse results concerning reductions of any class K > ε { NP. Mod₁P. PP. C = P} to sparse sets for various reducibilities.