Premium
On existence of complete sets for bounded reducibilities
Author(s) -
Bulitko Valeriy,
Bulitko Vadim
Publication year - 2003
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200310061
Subject(s) - recursively enumerable language , oracle , mathematics , hierarchy , set (abstract data type) , bounded function , combinatorics , discrete mathematics , computer science , mathematical analysis , software engineering , economics , market economy , programming language
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)