Minimal Pairs in the C.E. Truth-table Degrees
Rodney G. Downey, Keng Meng Ng · 2015
Strong reducibilities such as the m-reducibility have been around implicitly, if not explicitly, since the dawn of computability theory. The explicit recognition of the existence of differing kinds of oracle access mechanisms began with the seminal work of Post [12]. Of interest to us from Post’s paper are the so-called tabular reducibilities ≤tt, truth table reducibility, and