Automatically assigned DDC number: 004

Manually assigned DDC number: 51132

Number of references: 8

Title: Polynomial-Time Semi-Rankable Sets

Author:

Author:

Author:

Subject: Lane A. Hemaspaandra,Mohammed J. Zaki,Marius Zimand Polynomial-Time Semi-Rankable Sets

Description: We study the polynomial-time semi-rankable sets (P-sr), the ranking analog of the P-selective sets. We prove that P-sr is a strict subset of the P-selective sets, and indeed that the two classes differ with respect to closure under complementation, closure under union with P sets, closure under join with P sets, and closure under P-isomorphism. While P=poly is equal to the closure of P-selective sets under polynomial-time Turing reductions, we build a tally set that is not polynomial-time reducible to any P-sr set. We also show that though P-sr falls between the P-rankable and the weakly-P-rankable sets in its inclusiveness, it equals neither of these classes. Key words: semi-feasible sets, P-selectivity, ranking, closure properties, NNT. Research supported grants NSF-INT-9116781/JSPS-ENG-207, NSF-CCR-8957604, and NSF-CCR-9322513. y Research supported in part by ONR research grant no. N00014-92-J-1801 (in conjunction with ARPA Research in Information Science and Technology - High ...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1996-02-15

Pubyear: 1995

Format: ps

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

Source: ftp://ftp.cs.rochester.edu/pub/papers/theory/96.tr584rev.Polynomial-time_semi-rankable_sets.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="/132943.html"   Type="article"   CiteSeer_Book="Electronic   Colloquium   on   Computational   Complexity   ECCC"   CiteSeer_Volume=""   Title="Some   Connections   between   Bounded   Query   Classes   and   Non-Uniform   Complexity,">

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

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

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

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

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

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

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

            <identifier   Org="ISBN:0818656727"   Paper_ID="/132943.html"   Extracted="0818656727"   DDC="004.015113"   Normalized_DDC="004015113"   Normalized_Weight="0.07142857142857142"   />

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

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

            <identifier   Org="ISBN:0897913973"   Paper_ID="/132943.html"   Extracted="0897913973"   />

            <identifier   Org="ISBN:0897915119"   Paper_ID="/132943.html"   Extracted="0897915119"   />

            <identifier   Org="ISBN:3540228233"   Paper_ID="/132943.html"   Extracted="3540228233"   DDC="004.1"   Normalized_DDC="0041"   Normalized_Weight="0.07142857142857142"   />

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

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

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

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

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

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

      </rec>

      <rec   ID="/552485.html"   Type="article"   CiteSeer_Book="Journal   of   the   ACM"   CiteSeer_Volume="39"   Title="Lower   Bounds   for   the   Low   Hierarchy,">

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

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

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

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

            <identifier   Org="ISBN:0818656727"   Paper_ID="/552485.html"   Extracted="0818656727"   DDC="004.015113"   Normalized_DDC="004015113"   Normalized_Weight="0.08333333333333333"   />

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

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

            <identifier   Org="ISBN:3540424946"   Paper_ID="/552485.html"   Extracted="3540424946"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.08333333333333333"   />

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

            <identifier   Org="ISBN:3540552103"   Paper_ID="/552485.html"   Extracted="3540552103"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.08333333333333333"   />

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

            <identifier   Org="ISBN:3540562796"   Paper_ID="/552485.html"   Extracted="3540562796"   DDC="004/.01/5118"   Normalized_DDC="004015118"   Normalized_Weight="0.08333333333333333"   />

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

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

            <identifier   Org="ISBN:3540613323"   Paper_ID="/552485.html"   Extracted="3540613323"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.08333333333333333"   />

      </rec>

      <rec   ID="/606419.html"   Type="article"   CiteSeer_Book="Information   Processing   Letters"   CiteSeer_Volume="48"   Title="Twenty   Questions   to   a   P-Selector,">

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

            <identifier   Org="ISBN:3540287027"   Paper_ID="/606419.html"   Extracted="3540287027"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540422005"   Paper_ID="/606419.html"   Extracted="3540422005"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.25"   />

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

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

      </rec>

      <rec   ID="/178859.html"   Type="article"   CiteSeer_Book="Information   Processing   Letters"   CiteSeer_Volume="57"   Title="Scalability   and   the   Isomorphism   Problem,">

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

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

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

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

      </rec>

      <rec   ID="/109439.html"   Type="inproceedings"   CiteSeer_Book="ISAAC   5th   International   Symposium   on   Algorithms   and   Computation   formerly   SIGAL   International   Symposium   on   Algorithms   Organized   by   Special   Interest   Group   on   Algorithms   SIGAL   of   the   Information   Processing   Society   of   Japan   IPSJ   and   the   Technical   Group   on   Theoretical   Foundation   of   Computing   of   the   Institute   of   Electronics   Information   and   Communication   Engineers   IEICE"   CiteSeer_Volume=""   Title="Computing   Solutions   Uniquely   Collapses   the   Polynomial   Hierarchy,">

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

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

            <identifier   Org="ISBN:0818656727"   Paper_ID="/109439.html"   Extracted="0818656727"   DDC="004.015113"   Normalized_DDC="004015113"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540006230"   Paper_ID="/109439.html"   Extracted="3540006230"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540212582"   Paper_ID="/109439.html"   Extracted="3540212582"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:354031198X"   Paper_ID="/109439.html"   Extracted="354031198X"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540422005"   Paper_ID="/109439.html"   Extracted="3540422005"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540424946"   Paper_ID="/109439.html"   Extracted="3540424946"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07692307692307693"   />

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

            <identifier   Org="ISBN:3540613323"   Paper_ID="/109439.html"   Extracted="3540613323"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07692307692307693"   />

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

            <identifier   Org="ISBN:3540645705"   Paper_ID="/109439.html"   Extracted="3540645705"   DDC="004/.01/5113"   Normalized_DDC="004015113"   Normalized_Weight="0.07692307692307693"   />

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

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

            <identifier   Org="ISBN:3540694056"   Paper_ID="/109439.html"   Extracted="3540694056"   />

      </rec>

      <rec   ID="/22529.html"   Type="article"   CiteSeer_Book="Journal   of   Computer   and   System   Sciences"   CiteSeer_Volume="55"   Title="Universally   Serializable   Computation,">

            <identifier   Org="ISBN:0546654835"   Paper_ID="/22529.html"   Extracted="0546654835"   />

            <identifier   Org="ISBN:3540633863"   Paper_ID="/22529.html"   Extracted="3540633863"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:3540664084"   Paper_ID="/22529.html"   Extracted="3540664084"   DDC="001.64"   Normalized_DDC="00164"   Normalized_Weight="0.3333333333333333"   />

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

      </rec>

      <rec   ID="/173380.html"   Type="techreport"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Polynomial-Time   Membership   Comparable   Sets,">

            <identifier   Org="ISBN:0444828419"   Paper_ID="/173380.html"   Extracted="0444828419"   DDC="511.352"   Normalized_DDC="511352"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0521635500"   Paper_ID="/173380.html"   Extracted="0521635500"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.1"   />

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

            <identifier   Org="ISBN:0780342674"   Paper_ID="/173380.html"   Extracted="0780342674"   DDC="511"   Normalized_DDC="511"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0780356853"   Paper_ID="/173380.html"   Extracted="0780356853"   />

            <identifier   Org="ISBN:0818656727"   Paper_ID="/173380.html"   Extracted="0818656727"   DDC="004.015113"   Normalized_DDC="004015113"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0818683961"   Paper_ID="/173380.html"   Extracted="0818683961"   />

            <identifier   Org="ISBN:0824700260"   Paper_ID="/173380.html"   Extracted="0824700260"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.1"   />

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

            <identifier   Org="ISBN:3540206957"   Paper_ID="/173380.html"   Extracted="3540206957"   DDC="004.015181"   Normalized_DDC="004015181"   Normalized_Weight="0.1"   />

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

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

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

      </rec>

      <rec   ID="/41369.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Selectivity   and   self-reducibility:   New   characterizations   of   complexity   classes,"   />

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Polynomial-Time   Semi-Rankable   Sets">

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

            <identifier   Org="ISBN:3540422005"   Paper_ID="SELF"   Extracted="3540422005"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540424946"   Paper_ID="SELF"   Extracted="3540424946"   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"   />

      </rec>

</references_metadata>

www.000webhost.com