Tally NP sets and easy census functions

Judy Goldsmith, Mitsunori Ogihara, Jörg Rothe

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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 #P 1 ⊆ FP, where #P1 is the class of functions that count the witnesses for tally NP sets. We prove that every #P1 PH function can be computed in FP#p1 #p1. 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 #P1 ⊆ FP implies P = BPP and PH ⊆ MODkP for each k ≥ 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.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 1998 - 23rd International Symposium, MFCS 1998, Proceedings
EditorsLubos Brim, Jozef Gruska, Jiri Zlatuska
Number of pages10
StatePublished - 1998
Event23rd International Symposium on the Mathematical Foundations of Computer Science, MFCS 1998 - Brno, Czech Republic
Duration: Aug 24 1998Aug 28 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1450 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd International Symposium on the Mathematical Foundations of Computer Science, MFCS 1998
Country/TerritoryCzech Republic

Bibliographical note

Funding Information:
1Supported in part by NSF Grant CCR-9610348. 2Supported in part by NSF CAREER Award CCR-9701911. 3Supported in part by Grants NSF-INT-9513368 DAAD-315-PRO-fo-ab, NSF-CCR-9322513, and NSF-INT-9815095 DAAD-315-PPP-gu-ab, and by a NATO Postdoctoral Science Fellowship from the Deutscher Akademischer Austauschdienst (‘‘Gemeinsames Hochschulsonderprogramm III von Bund und Landern’’). Work done in part while visiting the University of Rochester and the University of Kentucky.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Tally NP sets and easy census functions'. Together they form a unique fingerprint.

Cite this