Abstract
Scalable sets are defined and their properties studied. It is shown that the set of scalable sets is the isomorphism closure of the set of rankable sets and that every scalable set is P-isomorphic to some rankable set. Scalable sets coincide with P-printable sets when sparse, and with P-paddable sets when thick. Using scalability as a tool, the P-isomorphism question for polynomial-time computable sets of similar densities is examined.
| Original language | English |
|---|---|
| Pages (from-to) | 137-143 |
| Number of pages | 7 |
| Journal | Information Processing Letters |
| Volume | 57 |
| Issue number | 3 |
| DOIs | |
| State | Published - Feb 12 1996 |
Bibliographical note
Funding Information:* Corresponding author. Email: [email protected]. This research was supported in part by NSF grants CCR-9103055 and CCR-9400229. i This research was supportedi n part by NSF grants RII-9003056 and CCR-93 15354.
Funding
* Corresponding author. Email: [email protected]. This research was supported in part by NSF grants CCR-9103055 and CCR-9400229. i This research was supportedi n part by NSF grants RII-9003056 and CCR-93 15354.
| Funders | Funder number |
|---|---|
| National Science Foundation (NSF) | CCR-9103055, CCR-93 15354, CCR-9400229, RII-9003056 |
Keywords
- Computational complexity
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications