Tally NP Sets and Easy Census Functions

Judy Goldsmith, Mitsunori Ogihara, Joerg Rothe

We study the question of whether every P set has an easy (i.e., polynomial-time computable) census function. We characterize this question in terms of unlikely collapses of languag…