Accession Number : ADA300061

Title :   Polynomial-Time Semi-Rankable 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 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, and closure under join with P sets. 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.

Descriptors :   *POLYNOMIALS, *SET THEORY, CLOSURES.

Subject Categories : Numerical Mathematics
      Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE