On existence of complete sets for bounded reducibilities | Zendy

Bulitko Valeriy | Zendy; Bulitko Vadim | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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)

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research