Accession Number:

ADA300061

Title:

Polynomial-Time Semi-Rankable Sets.

Descriptive Note:

Technical rept.,

Corporate Author:

ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Report Date:

1995-05-01

Pagination or Media Count:

14.0

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.

Subject Categories:

  • Numerical Mathematics
  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE