Referensi untuk Turing untuk banyak-satu pengurangan

Saya mencari referensi tentang `mengurangi 'pengurangan Turing ke banyak-satu pengurangan. Dalam benak saya ada pernyataan tentang bentuk berikut (pernyataan yang serupa juga akan memuaskan saya):

Dalil. Jika , maka A ≤ 2 f m B t t .$\mathsf{A}\leq_T^f \mathsf{B}$$\mathsf A\leq_m^{2^f}\mathsf B^{tt}$

di mana " " dan " ≤ f m " merupakan masing-masing Turing dan banyak-satu pengurangan deterministik waktu f ( n ) , dan " B t t " menunjukkan sebuah tabel `kebenaran' varian dari bahasa B , yang mengevaluasi sebuah Boolean kombinasi cek " x ∈ B ".$\leq_T^f$$\leq_m^f$$f(n)$$\mathsf{B}^{tt}$$\mathsf{B}$$x\in\mathsf{B}$

Gagasan bukti untuk pernyataan: Simulasikan oracle yang dibatasi waktu digunakan dalam pengurangan Turing: cukup mudah untuk mendapatkan transduser Turing nondeterministik juga dalam waktu f ( n ) yang menebak jawaban B oracle dan menulis konjungsi cek " x ∈ B " atau " x ∉ B " pada output, untuk dievaluasi oleh B t t mesin. Transduser ini dapat ditentukan dengan menjelajahi kedua hasil panggilan oracle, dan menanganinya melalui disjungsi dalam output; sekarang berfungsi dalam waktu $f(n)$$f(n)$$\mathsf B$$x\in\mathsf B$$x\not\in\mathsf{B}$$\mathsf B^{tt}$ .$2^{f(n)}$

Anehnya, sepertinya saya tidak dapat menemukan hasil terkait dalam buku teks kompleksitas.

Edit: berganti nama menjadi " " menjadi " B t t " untuk menekankan hubungan dengan tabel kebenaran, sebagai keluar menunjuk oleh @ MarkusBläser.$A\mathsf B$$\mathsf B^{tt}$

Saya cukup yakin Anda dapat menemukan ini dalam buku Bounded Queries in Recursion Theory oleh Martin dan Gasarch, tetapi saya tidak memiliki akses ke salinan sekarang untuk memeriksa.

$2^f$

PS - Saya setuju dengan komentar M. Blaser: Anda pada dasarnya berbicara tentang pengurangan tabel kebenaran tanpa menggunakan terminologi itu.