𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On existence of complete sets for bounded reducibilities

✍ Scribed by Valeriy Bulitko; Vadim Bulitko

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
165 KB
Volume
49
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

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 hierarchy of the bounds on oracle access is built. As the bounds become stricter, complete sets lose certain characteristics and eventually vanish. (Β© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

πŸ“œ SIMILAR VOLUMES

Do there exist complete sets for promise
Do there exist complete sets for promise classes?
✍ Olaf Beyersdorff; Zenon Sadowski πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 203 KB

In this paper we investigate the following two questions: Q1: Do there exist optimal proof systems for a given language L? Q2: Do there exist complete problems for a given promise class C? For concrete languages L (such as TAUT or SAT) and concrete promise classes C (such as NP ∩ coNP, UP, BPP, dis

On the existence of bounded noncontinuab
On the existence of bounded noncontinuable solutions
✍ Miroslav BartuΕ‘ek πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 154 KB

## Abstract This paper presents necessary and sufficient conditions for an __n__ ‐th order differential equation to have a non‐continuable solution with finite limits of its derivatives up to the order __l__ at the right‐hand end point of the interval of its definition, __l__ ≀ __n__ – 2 (Β© 2010 WI

On Axioms of Conditional Set Existence
On Axioms of Conditional Set Existence
✍ Hao Wang πŸ“‚ Article πŸ“… 1967 πŸ› John Wiley and Sons 🌐 English βš– 269 KB

ON AXIOMS OF CONDITIONAL SET EXISTENCE1) by HAO WANU in Cambridge, Mass. (U.S.A.) ## 1. Outline of arguments I n what follows, the (restricted) predicate calculus with equality is assumed throughout. Let ( U ! u ) H u be short for (w) ( u ) ((Hw A H u ) 13 w = u ) , ( E ! y ) H y be short for (Ey)

Bounds for linear functionals on convex
Bounds for linear functionals on convex sets
✍ Walter Roth πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 187 KB

## Abstract We consider continuous monotone linear functionals on a locally convex ordered topological vector space that are sandwiched between a given \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$(\mathbb R\cup \lbrace +\infty \rbrace )$\end{document}‐valued subline