SELF-REDUCIBLE, P-SELECTIVE, NEAR-TESTABLE, AND P-CHEATABLE SETS: THE EFFECT OF INTERNAL STRUCTURE ON THE COMPLEXITY OF A SET.

Judy Goldsmith, Deborah Joseph, Paul Young

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

14 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationUnknown Host Publication Title
Pages50-59
Number of pages10
StatePublished - 1987

ASJC Scopus subject areas

  • Engineering (all)

Fingerprint

Dive into the research topics of 'SELF-REDUCIBLE, P-SELECTIVE, NEAR-TESTABLE, AND P-CHEATABLE SETS: THE EFFECT OF INTERNAL STRUCTURE ON THE COMPLEXITY OF A SET.'. Together they form a unique fingerprint.

Cite this