Title :
SPARSE reduces conjunctively to TALLY
Author :
Buhrman, Harry ; Longpre, Luc ; Spaan, Edith
Author_Institution :
Amsterdam Univ., Netherlands
Abstract :
Polynomials over finite fields are used to conjunctively reduce any sparse set to a tally set. This leads to the derivation of new results and to new simple proofs of known results about various classes that lie between P and P/poly
Keywords :
computational complexity; polynomials; set theory; SPARSE; TALLY; computational complexity; conjunctive reduction; finite fields; polynomials; sparse set; tally set; Books; Computer science; Galois fields; Mathematics; Polynomials; TV; Terminology;
Conference_Titel :
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
Conference_Location :
San Diego, CA
Print_ISBN :
0-8186-4070-7
DOI :
10.1109/SCT.1993.336525
