On the complexity-relativized strong reducibilites |
| |
Authors: | Jari Talja |
| |
Institution: | 1. Department of Philosophy, University of Turku, 20500, Turku 50, Finland
|
| |
Abstract: | This paper discusses refinements of the natural ordering of them-degrees (1-degrees) of strong recursive reducibility classes. Such refinements are obtained by posing complexity conditions on the reduction function. The discussion uses the axiomatic complexity theory and is hence very general. As the main result it is proved that if the complexity measure is required to be linearly bounded (and space-like), then a natural class of refinements forms a lattice with respect to a natural ordering upon them. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|