SCALABILITY AND THE ISOMORPHISM-PROBLEM

Authors
GOLDSMITH J HOMER S
Citation
J. Goldsmith et S. Homer, SCALABILITY AND THE ISOMORPHISM-PROBLEM, Information processing letters, 57(3), 1996, pp. 137-143
Citations number
15
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
57
Issue
3
Year of publication
1996
Pages
137 - 143
Database
ISI
SICI code
0020-0190(1996)57:3<137:SATI>2.0.ZU;2-J
Abstract
Scalable sets are defined and their properties studied, It is shown th at the set of scalable sets is the isomorphism closure of the set of r ankable sets and that every scalable set is P-isomorphic to some ranka ble set. Scalable sets coincide with P-printable sets when sparse, and with P-paddable sets when thick. Using scalability as a tool, the P-i somorphism question for polynomial-time computable sets of similar den sities is examined.