SPARSE reduces conjunctively to TALLY. (English) Zbl 0830.68042

Summary: Polynomials over finite fields are used to show that any sparse set can conjunctively reduce to a tally set. This leads to new results and to simple proofs of known results about various classes that lie between P and P/poly.


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI Link