
Accession Number : ADA300061
Title : PolynomialTime SemiRankable Sets.
Descriptive Note : Technical rept.,
Corporate Author : ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE
Personal Author(s) : Hemaspaandra, Lane A. ; Zaki, Mohammed J. ; Zimand, Marius
PDF Url : ADA300061
Report Date : MAY 1995
Pagination or Media Count : 14
Abstract : We study the polynomialtime semirankable sets (Psr), the ranking analog of the Pselective sets. We prove that Psr is a strict subset of the Pselective sets, and indeed that the two classes differ with respect to closure under complementation, closure under union with P sets, and closure under join with P sets. We also show that though Psr falls between the Prankable and the weaklyPrankable sets in its inclusiveness, it equals neither of these classes.
Descriptors : *POLYNOMIALS, *SET THEORY, CLOSURES.
Subject Categories : Numerical Mathematics
Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE