Agrawal, M. ; Arvind, V.
(1996)
*Geometric sets of low information content*
Theoretical Computer Science, 158
(1-2).
pp. 193-219.
ISSN 0304-3975

Full text not available from this repository.

Official URL: http://linkinghub.elsevier.com/retrieve/pii/030439...

Related URL: http://dx.doi.org/10.1016/0304-3975(95)00073-9

## 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_{1} (and LT_{1}) 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_{1} and LT_{1}. 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_{1} or LT_{1} is already in P. As a consequence we derive that if a complete set for any class K > ε { NP. Mod_{1}P. PP. C = P} many-one reduces to a set in ELT_{1} or LT_{1} 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_{1} or LT_{1}. Thus, our results concerning reductions to ELT_{1} and LT_{1} subsume the strongest existing collapse results concerning reductions of any class K > ε { NP. Mod_{1}P. PP. C = P} to sparse sets for various reducibilities.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Elsevier Science. |

ID Code: | 20242 |

Deposited On: | 20 Nov 2010 14:48 |

Last Modified: | 10 May 2011 07:33 |

Repository Staff Only: item control page