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>