| Abstrakt: |
Let be a binary relation between sets of integers, and be a Post reducibility, i.e. a reflexive and transitive relation between sets of integers such that if then the computational complexity of recognition of elements of is easier than (or equal to) the recognition of elements of . Suppose that for a class of arithmetical sets, which have an effective enumeration , there are -complete sets, i.e. such sets that for any , . Earlier we considered completeness criteria for such reducibilities roughly of the following type: For any , is -complete if and only if there is a function , defined on such that and for all . This means that for any set , if it is non-complete, then any function has a fixed-point : . In this paper we introduce a notion of fixed-point selection function for sequences of such sets and study their complexity characteristics. [ABSTRACT FROM AUTHOR] |
Full text from SpringerLink