𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A New Reducibility between Turing- and wtt-Reducibility

✍ Scribed by Sui Yuefei

Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
233 KB
Volume
40
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A new reducibility between Turing and weak truth‐table reducibility is defined, which gives an affirmative answer to the open question about the existence of such an intermediate reducibility proposed formally by M. Stob.

Mathematics Subject Classification: 03D25.

πŸ“œ SIMILAR VOLUMES

BOUNDS IN THE TURING REDUCIBILITY OF FUN
BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
✍ Karol Habart; K. Habart πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 374 KB

## Abstract A hierarchy of functions with respect to their role as bounds in the Turing reducibility of functions is introduced and studied. This hierarchy leads to a certain notion of incompressibility of sets which is also investigated.

On sparseness and Turing reducibility ov
On sparseness and Turing reducibility over the reals
✍ Felipe Cucker πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 517 KB

We prove some results about existence of NP-complete and NP-hard (for Turing reductions) sparse sets on different settings over the real numbers.

A survey on snarks and new results: Prod
A survey on snarks and new results: Products, reducibility and a computer search
✍ Cavicchioli, A.; Meschiari, M.; Ruini, B.; Spaggiari, F. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 566 KB

In this paper we survey recent results and problems of both theoretical and algorithmic character on the construction of snarks-non-trivial cubic graphs of class two, of cyclic edge-connectivity at least 4 and with girth β‰₯ 5. We next study the process, also considered by Cameron, Chetwynd, Watkins,