✦ LIBER ✦

Nondeterministic bounded query reducibilities

✍ Scribed by Richard Beigel; William Gasarch; Jim Owings

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 776 KB
Volume: 41
Category: Article
ISSN: 0168-0072
DOI: 10.1016/0168-0072(89)90010-9

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On bounded query machines

✍ Jose L. Balcázar; Ronald V. Book; Uwe Schöning 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 452 KB

Post's Problem for Reducibilities of Bou

Post's Problem for Reducibilities of Bounded Complexity

✍ Valeriy K. Bulitko 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

On existence of complete sets for bounde

On existence of complete sets for bounded reducibilities

✍ Valeriy Bulitko; Vadim Bulitko 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB

## Abstract Classical reducibilities have complete sets __U__ that any recursively enumerable set can be reduced to __U__. This paper investigates existence of complete sets for reducibilities with limited oracle access. Three characteristics of classical complete sets are selected and a natural hi

Bounded query classes and the difference

Bounded query classes and the difference hierarchy

✍ Richard Beigel; William I. Gasarch; Louise Hay 📂 Article 📅 1989 🏛 Springer 🌐 English ⚖ 817 KB

Frequency computation and bounded querie

Frequency computation and bounded queries

✍ Richard Beigel; William Gasarch; Efim Kinber 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 1014 KB

Bounded truth table does not reduce the

Bounded truth table does not reduce the one-query tautologies to a random oracle

✍ Toshio Suzuki 📂 Article 📅 2005 🏛 Springer 🌐 English ⚖ 171 KB