Tally NP sets and easy census functions

Judy Goldsmith; Mitsunori Ogihara; Jörg Rothe

doi:10.1006/inco.1999.2810

Tally NP sets and easy census functions

Judy Goldsmith, Mitsunori Ogihara, Jörg Rothe

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

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₁ ⊆ FP, where #P₁ is the class of functions that count the witnesses for tally NP sets. We prove that every #P₁^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 #P₁ ⊆ FP implies P = BPP and PH ⊆ MOD_kP for each k ≥ 2. 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 language	English
Pages (from-to)	29-52
Number of pages	24
Journal	Information and Computation
Volume	158
Issue number	1
DOIs	https://doi.org/10.1006/inco.1999.2810
State	Published - 2000

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
Information Systems
Computer Science Applications
Computational Theory and Mathematics

Access to Document

10.1006/inco.1999.2810

Cite this

@article{f0e15026df2b4c118ec5e52f9ecf37ee,

title = "Tally NP sets and easy census functions",

abstract = "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 #P1 ⊆ FP, where #P1 is the class of functions that count the witnesses for tally NP sets. We prove that every #P1PH 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. 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.",

author = "Judy Goldsmith and Mitsunori Ogihara and J{\"o}rg Rothe",

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 ({\textquoteleft}{\textquoteleft}Gemeinsames Hochschulsonderprogramm III von Bund und Landern{\textquoteright}{\textquoteright}). Work done in part while visiting the University of Rochester and the University of Kentucky.",

year = "2000",

doi = "10.1006/inco.1999.2810",

language = "English",

volume = "158",

pages = "29--52",

number = "1",

}

TY - JOUR

T1 - Tally NP sets and easy census functions

AU - Goldsmith, Judy

AU - Ogihara, Mitsunori

AU - Rothe, Jörg

N1 - 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.

PY - 2000

Y1 - 2000

N2 - 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 #P1 ⊆ FP, where #P1 is the class of functions that count the witnesses for tally NP sets. We prove that every #P1PH 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. 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.

AB - 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 #P1 ⊆ FP, where #P1 is the class of functions that count the witnesses for tally NP sets. We prove that every #P1PH 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. 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.

UR - http://www.scopus.com/inward/record.url?scp=0034629930&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034629930&partnerID=8YFLogxK

U2 - 10.1006/inco.1999.2810

DO - 10.1006/inco.1999.2810

M3 - Article

AN - SCOPUS:0034629930

SN - 0890-5401

VL - 158

SP - 29

EP - 52

JO - Information and Computation

JF - Information and Computation

IS - 1

ER -

Tally NP sets and easy census functions

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this