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>

www.000webhost.com