TY - GEN
T1 - SELF-REDUCIBLE, P-SELECTIVE, NEAR-TESTABLE, AND P-CHEATABLE SETS
T2 - THE EFFECT OF INTERNAL STRUCTURE ON THE COMPLEXITY OF A SET.
AU - Goldsmith, Judy
AU - Joseph, Deborah
AU - Young, Paul
PY - 1987
Y1 - 1987
N2 - The relationship between certain structural properties of a set and the set's computational complexity is discussed. Four classes of sets are studied for which the membership question for one element of the domain can be related to the membership question of other smaller (with regard to some ordering) elements: self-reducible sets, p-selective sets, near-testable sets and p-cheatable sets. The results suggest that a continuing systematic study of the relationship between this type of internal structure and the computational complexity of a set is in order.
AB - The relationship between certain structural properties of a set and the set's computational complexity is discussed. Four classes of sets are studied for which the membership question for one element of the domain can be related to the membership question of other smaller (with regard to some ordering) elements: self-reducible sets, p-selective sets, near-testable sets and p-cheatable sets. The results suggest that a continuing systematic study of the relationship between this type of internal structure and the computational complexity of a set is in order.
UR - http://www.scopus.com/inward/record.url?scp=0023244345&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0023244345&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0023244345
SN - 0818607947
SP - 50
EP - 59
BT - Unknown Host Publication Title
ER -