Tally NP Sets and Easy Census Functions
| dc.creator | Goldsmith, Judy | |
| dc.creator | Ogihara, Mitsunori | |
| dc.creator | Rothe, Joerg | |
| dc.date | 1998-09-01 | |
| dc.date.accessioned | 2026-07-07T03:23:29Z | |
| dc.date.available | 2026-07-07T03:23:29Z | |
| dc.description | 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 language and function classes such as the containment of #P_1 in FP, where #P_1 is the class of functions that count the witnesses for tally NP sets. We prove that every #P_{1}^{PH} function can be computed in FP^{#P_{1}^{#P_{1}}}. Consequently, every P set has an easy census function if and only if every set in the polynomial hierarchy does. We show that the assumption of #P_1 being contained in FP implies P = BPP and that PH is contained in MOD_{k}P for each k \geq 2, which provides further evidence that not all sets in P have an easy census function. We also relate a set's property of having an easy census function to other well-studied properties of sets, such as rankability and scalability (the closure of the rankable sets under P-isomorphisms). Finally, we prove that it is no more likely that the census function of any set in P can be approximated (more precisely, can be n^α-enumerated in time n^β for fixed αand β) than that it can be precisely computed in polynomial time. | |
| dc.description | 24 pages | |
| dc.identifier | https://arxiv.org/abs/cs/9809002 | |
| dc.identifier | http://arxiv.org/abs/cs/9809002 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32957 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | Tally NP Sets and Easy Census Functions | |
| dc.type | text |