Polynomial-Time Semi-Rankable Sets.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1995
- Accession Number
- ADA300061
Entities
People
- Lane A. Hemaspaandra
- Marius Zimand
- Mohammed J. Zaki
Organizations
- University of Rochester