RUS  ENG
Full version
JOURNALS // Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya // Archive

Izv. Akad. Nauk SSSR Ser. Mat., 1985 Volume 49, Issue 1, Pages 3–31 (Mi im1345)

This article is cited in 1 paper

Boolean classes of Turing reductions

V. K. Bulitko


Abstract: A relation of sub-Turing reducibility is defined for each class of ordered pairs of Boolean functions. Criteria are found for the transitivity and reflexivity of the reducibility relation defined by a class of ordered pairs of Boolean functions. The place of a number of familiar reducibilities in the framework of this classification is indicated.
Bibliography: 10 titles.

UDC: 517.11+518.5

MSC: 03D20, 03D30

Received: 23.11.1982


 English version:
Mathematics of the USSR-Izvestiya, 1986, 26:1, 1–29

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024