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 -