Automatically assigned DDC number: 004
Manually assigned DDC number: 0040151

Number of references: 8

Title: Tally NP Sets and Easy Census Functions

Author:

Author:

Author:

Subject: Judy Goldsmith,Mitsunori Ogihara,Jorg Rothe Tally NP Sets and Easy Census Functions

Description: We study the question of whether every P set has an easy (i.e., polynomialtime computable) census function. We characterize this question in terms of unlikely collapses of language and function classes such as #P 1 ` FP, where #P 1 is the class of functions that count the witnesses for tally NP sets. We prove that every #P PH 1 function can be computed in FP #P #P 1 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 #P 1 ` FP implies P = BPP and PH ` MOD k P 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 ff -e...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1998-03-24

Pubyear: 1998

Format: ps

Identifier: http://citeseer.ist.psu.edu/173194.html

Source: http://hypatia.dcs.qmw.ac.uk/data/edu/cs.rochester.edu/theory/98.tr684.Tally_NP_sets_and_easy_census_functions.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml version="1.0" encoding="UTF-8"?>

<references_metadata>

<rec ID="/550412.html" Type="article" CiteSeer_Book="Mathematical Systems Theory" CiteSeer_Volume="24" Title="Limitations of the Upward Separation Technique,">

<identifier Org="ISBN:0818619589" Paper_ID="/550412.html" Extracted="0818619589" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.125" />

<identifier Org="ISBN:0818624477" Paper_ID="/550412.html" Extracted="0818624477" />

<identifier Org="ISBN:3540221476" Paper_ID="/550412.html" Extracted="3540221476" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.125" />

<identifier Org="ISBN:354051371X" Paper_ID="/550412.html" Extracted="354051371X" />

<identifier Org="ISBN:3540520481" Paper_ID="/550412.html" Extracted="3540520481" />

<identifier Org="ISBN:3540558403" Paper_ID="/550412.html" Extracted="3540558403" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540565035" Paper_ID="/550412.html" Extracted="3540565035" DDC="004" Normalized_DDC="004" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540626166" Paper_ID="/550412.html" Extracted="3540626166" DDC="004" Normalized_DDC="004" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540637745" Paper_ID="/550412.html" Extracted="3540637745" DDC="004" Normalized_DDC="004" Normalized_Weight="0.125" />

<identifier Org="ISBN:354065691X" Paper_ID="/550412.html" Extracted="354065691X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540674195" Paper_ID="/550412.html" Extracted="3540674195" DDC="003" Normalized_DDC="003" Normalized_Weight="0.125" />

</rec>

<rec ID="/33951.html" Type="inproceedings" CiteSeer_Book="Structure in Complexity Theory Conference" CiteSeer_Volume="" Title="Gap-Definable Counting Classes,">

<identifier Org="ISBN:0387949739" Paper_ID="/33951.html" Extracted="0387949739" DDC="004/.01/5113" Normalized_DDC="004015113" Normalized_Weight="0.0625" />

<identifier Org="ISBN:0818622555" Paper_ID="/33951.html" Extracted="0818622555" />

<identifier Org="ISBN:0818673877" Paper_ID="/33951.html" Extracted="0818673877" />

<identifier Org="ISBN:1402071817" Paper_ID="/33951.html" Extracted="1402071817" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />

<identifier Org="ISBN:1402081405" Paper_ID="/33951.html" Extracted="1402081405" DDC="004.01" Normalized_DDC="00401" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540206809" Paper_ID="/33951.html" Extracted="3540206809" DDC="005" Normalized_DDC="005" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540221476" Paper_ID="/33951.html" Extracted="3540221476" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.0625" />

<identifier Org="ISBN:354022856X" Paper_ID="/33951.html" Extracted="354022856X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540406719" Paper_ID="/33951.html" Extracted="3540406719" />

<identifier Org="ISBN:3540424997" Paper_ID="/33951.html" Extracted="3540424997" DDC="621.39/5" Normalized_DDC="621395" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540565035" Paper_ID="/33951.html" Extracted="3540565035" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540569391" Paper_ID="/33951.html" Extracted="3540569391" />

<identifier Org="ISBN:3540583254" Paper_ID="/33951.html" Extracted="3540583254" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540633855" Paper_ID="/33951.html" Extracted="3540633855" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540638768" Paper_ID="/33951.html" Extracted="3540638768" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540642307" Paper_ID="/33951.html" Extracted="3540642307" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540648240" Paper_ID="/33951.html" Extracted="3540648240" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540664122" Paper_ID="/33951.html" Extracted="3540664122" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540671595" Paper_ID="/33951.html" Extracted="3540671595" DDC="511.8" Normalized_DDC="5118" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540674195" Paper_ID="/33951.html" Extracted="3540674195" DDC="003" Normalized_DDC="003" Normalized_Weight="0.0625" />

</rec>

<rec ID="/304110.html" Type="inproceedings" CiteSeer_Book="" CiteSeer_Volume="" Title="Almost optimal lower bounds for small depth circuits,">

<identifier Org="ISBN:0769506755" Paper_ID="/304110.html" Extracted="0769506755" />

<identifier Org="ISBN:0818624701" Paper_ID="/304110.html" Extracted="0818624701" DDC="621.381" Normalized_DDC="621381" Normalized_Weight="0.1" />

<identifier Org="ISBN:0818640707" Paper_ID="/304110.html" Extracted="0818640707" />

<identifier Org="ISBN:0818643706" Paper_ID="/304110.html" Extracted="0818643706" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1" />

<identifier Org="ISBN:082183679X" Paper_ID="/304110.html" Extracted="082183679X" DDC="510" Normalized_DDC="51" Normalized_Weight="0.1" />

<identifier Org="ISBN:0897913078" Paper_ID="/304110.html" Extracted="0897913078" />

<identifier Org="ISBN:0897917855" Paper_ID="/304110.html" Extracted="0897917855" />

<identifier Org="ISBN:0897918886" Paper_ID="/304110.html" Extracted="0897918886" />

<identifier Org="ISBN:1402001983" Paper_ID="/304110.html" Extracted="1402001983" DDC="510/.3" Normalized_DDC="5103" Normalized_Weight="0.1" />

<identifier Org="ISBN:1581133499" Paper_ID="/304110.html" Extracted="1581133499" />

<identifier Org="ISBN:3540194886" Paper_ID="/304110.html" Extracted="3540194886" />

<identifier Org="ISBN:3540241310" Paper_ID="/304110.html" Extracted="3540241310" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540505172" Paper_ID="/304110.html" Extracted="3540505172" />

<identifier Org="ISBN:354051631X" Paper_ID="/304110.html" Extracted="354051631X" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540571639" Paper_ID="/304110.html" Extracted="3540571639" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540642307" Paper_ID="/304110.html" Extracted="3540642307" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540647813" Paper_ID="/304110.html" Extracted="3540647813" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540797084" Paper_ID="/304110.html" Extracted="3540797084" DDC="004.0947" Normalized_DDC="0040947" Normalized_Weight="0.1" />

</rec>

<rec ID="/182808.html" Type="article" CiteSeer_Book="SIAM J Comput" CiteSeer_Volume="28" Title="A Downward Collapse within the Polynomial Hierarchy,">

<identifier Org="ISBN:3519003155" Paper_ID="/182808.html" Extracted="3519003155" />

<identifier Org="ISBN:3540221476" Paper_ID="/182808.html" Extracted="3540221476" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.25" />

<identifier Org="ISBN:354065691X" Paper_ID="/182808.html" Extracted="354065691X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.25" />

<identifier Org="ISBN:3540674195" Paper_ID="/182808.html" Extracted="3540674195" DDC="003" Normalized_DDC="003" Normalized_Weight="0.25" />

<identifier Org="ISBN:3540771182" Paper_ID="/182808.html" Extracted="3540771182" />

<identifier Org="ISBN:3540797440" Paper_ID="/182808.html" Extracted="3540797440" DDC="005.82" Normalized_DDC="00582" Normalized_Weight="0.25" />

</rec>

<rec ID="/52676.html" Type="techreport" CiteSeer_Book="" CiteSeer_Volume="" Title="Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets,">

<identifier Org="ISBN:1402071817" Paper_ID="/52676.html" Extracted="1402071817" DDC="004" Normalized_DDC="004" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:3540221476" Paper_ID="/52676.html" Extracted="3540221476" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:3540281932" Paper_ID="/52676.html" Extracted="3540281932" DDC="004" Normalized_DDC="004" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:3540626166" Paper_ID="/52676.html" Extracted="3540626166" DDC="004" Normalized_DDC="004" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:3540664122" Paper_ID="/52676.html" Extracted="3540664122" DDC="004" Normalized_DDC="004" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:3540674195" Paper_ID="/52676.html" Extracted="3540674195" DDC="003" Normalized_DDC="003" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:3540797440" Paper_ID="/52676.html" Extracted="3540797440" DDC="005.82" Normalized_DDC="00582" Normalized_Weight="0.14285714285714285" />

</rec>

<rec ID="/165073.html" Type="techreport" CiteSeer_Book="" CiteSeer_Volume="" Title="Easy Sets and Hard Certificate Schemes,">

<identifier Org="ISBN:0769510531" Paper_ID="/165073.html" Extracted="0769510531" />

<identifier Org="ISBN:0769521207" Paper_ID="/165073.html" Extracted="0769521207" />

<identifier Org="ISBN:0818673877" Paper_ID="/165073.html" Extracted="0818673877" />

<identifier Org="ISBN:3540221476" Paper_ID="/165073.html" Extracted="3540221476" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540240586" Paper_ID="/165073.html" Extracted="3540240586" DDC="005.3" Normalized_DDC="0053" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540625925" Paper_ID="/165073.html" Extracted="3540625925" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540626166" Paper_ID="/165073.html" Extracted="3540626166" DDC="004" Normalized_DDC="004" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540648275" Paper_ID="/165073.html" Extracted="3540648275" DDC="004" Normalized_DDC="004" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540662006" Paper_ID="/165073.html" Extracted="3540662006" DDC="004" Normalized_DDC="004" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540679014" Paper_ID="/165073.html" Extracted="3540679014" DDC="004.0151" Normalized_DDC="0040151" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540797440" Paper_ID="/165073.html" Extracted="3540797440" DDC="005.82" Normalized_DDC="00582" Normalized_Weight="0.125" />

</rec>

<rec ID="/367234.html" Type="article" CiteSeer_Book="Journal of Computer and System Sciences" CiteSeer_Volume="44" Title="Turing Machines with Few Accepting Computations and Low Sets for {PP},">

<identifier Org="ISBN:0387529535" Paper_ID="/367234.html" Extracted="0387529535" DDC="004/.01/51" Normalized_DDC="0040151" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:0792343964" Paper_ID="/367234.html" Extracted="0792343964" DDC="511/.8" Normalized_DDC="5118" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:0818619589" Paper_ID="/367234.html" Extracted="0818619589" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:0818620722" Paper_ID="/367234.html" Extracted="0818620722" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:0818622555" Paper_ID="/367234.html" Extracted="0818622555" />

<identifier Org="ISBN:081862955X" Paper_ID="/367234.html" Extracted="081862955X" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:1402071817" Paper_ID="/367234.html" Extracted="1402071817" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540206809" Paper_ID="/367234.html" Extracted="3540206809" DDC="005" Normalized_DDC="005" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540221565" Paper_ID="/367234.html" Extracted="3540221565" DDC="512.7" Normalized_DDC="5127" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:354051371X" Paper_ID="/367234.html" Extracted="354051371X" />

<identifier Org="ISBN:3540514988" Paper_ID="/367234.html" Extracted="3540514988" />

<identifier Org="ISBN:3540522824" Paper_ID="/367234.html" Extracted="3540522824" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540557199" Paper_ID="/367234.html" Extracted="3540557199" DDC="005.13/1" Normalized_DDC="005131" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540562877" Paper_ID="/367234.html" Extracted="3540562877" DDC="005" Normalized_DDC="005" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540575685" Paper_ID="/367234.html" Extracted="3540575685" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540664122" Paper_ID="/367234.html" Extracted="3540664122" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:9810214626" Paper_ID="/367234.html" Extracted="9810214626" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />

</rec>

<rec ID="/42886.html" Type="techreport" CiteSeer_Book="" CiteSeer_Volume="" Title="Upward Separation for Few{P} and Related Classes," />

<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Tally NP Sets and Easy Census Functions">

<identifier Org="ISBN:3540221476" Paper_ID="SELF" Extracted="3540221476" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.25" />

<identifier Org="ISBN:3540648275" Paper_ID="SELF" Extracted="3540648275" DDC="004" Normalized_DDC="004" Normalized_Weight="0.25" />

<identifier Org="ISBN:3540674195" Paper_ID="SELF" Extracted="3540674195" DDC="003" Normalized_DDC="003" Normalized_Weight="0.25" />

<identifier Org="ISBN:3540797440" Paper_ID="SELF" Extracted="3540797440" DDC="005.82" Normalized_DDC="00582" Normalized_Weight="0.25" />

</rec>

</references_metadata>