SPARSE REDUCES CONJUNCTIVELY TO TALLY

Authors
BUHRMAN H HEMASPAANDRA E LONGPRE L
Citation
H. Buhrman et al., SPARSE REDUCES CONJUNCTIVELY TO TALLY, SIAM journal on computing, 24(4), 1995, pp. 673-681
Citations number
21
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
24
Issue
4
Year of publication
1995
Pages
673 - 681
Database
ISI
SICI code
0097-5397(1995)24:4<673:SRCTT>2.0.ZU;2-N
Abstract
Polynomials over finite fields are used to show that any sparse set ca n conjunctively reduce to a tally set. This leads to new results and t o simple proofs of known results about various classes that lie betwee n P and P/poly.