Cargando…

Bounded queries in recursion theory

One of the major concerns of theoretical computer science is the classifi­ cation of problems in terms of how hard they are. The natural measure of difficulty of a function is the amount of time needed to compute it (as a function of the length of the input). Other resources, such as space, have als...

Descripción completa

Detalles Bibliográficos
Autores principales: Gasarch, William I, Martin, Georgia A
Lenguaje:eng
Publicado: Springer 1999
Materias:
Acceso en línea:https://dx.doi.org/10.1007/978-1-4612-0635-4
http://cds.cern.ch/record/2006126
_version_ 1780946250774872064
author Gasarch, William I
Martin, Georgia A
author_facet Gasarch, William I
Martin, Georgia A
author_sort Gasarch, William I
collection CERN
description One of the major concerns of theoretical computer science is the classifi­ cation of problems in terms of how hard they are. The natural measure of difficulty of a function is the amount of time needed to compute it (as a function of the length of the input). Other resources, such as space, have also been considered. In recursion theory, by contrast, a function is considered to be easy to compute if there exists some algorithm that computes it. We wish to classify functions that are hard, i.e., not computable, in a quantitative way. We cannot use time or space, since the functions are not even computable. We cannot use Turing degree, since this notion is not quantitative. Hence we need a new notion of complexity-much like time or spac~that is quantitative and yet in some way captures the level of difficulty (such as the Turing degree) of a function.
id cern-2006126
institution Organización Europea para la Investigación Nuclear
language eng
publishDate 1999
publisher Springer
record_format invenio
spelling cern-20061262021-04-21T20:23:59Zdoi:10.1007/978-1-4612-0635-4http://cds.cern.ch/record/2006126engGasarch, William IMartin, Georgia ABounded queries in recursion theoryMathematical Physics and MathematicsOne of the major concerns of theoretical computer science is the classifi­ cation of problems in terms of how hard they are. The natural measure of difficulty of a function is the amount of time needed to compute it (as a function of the length of the input). Other resources, such as space, have also been considered. In recursion theory, by contrast, a function is considered to be easy to compute if there exists some algorithm that computes it. We wish to classify functions that are hard, i.e., not computable, in a quantitative way. We cannot use time or space, since the functions are not even computable. We cannot use Turing degree, since this notion is not quantitative. Hence we need a new notion of complexity-much like time or spac~that is quantitative and yet in some way captures the level of difficulty (such as the Turing degree) of a function.Springeroai:cds.cern.ch:20061261999
spellingShingle Mathematical Physics and Mathematics
Gasarch, William I
Martin, Georgia A
Bounded queries in recursion theory
title Bounded queries in recursion theory
title_full Bounded queries in recursion theory
title_fullStr Bounded queries in recursion theory
title_full_unstemmed Bounded queries in recursion theory
title_short Bounded queries in recursion theory
title_sort bounded queries in recursion theory
topic Mathematical Physics and Mathematics
url https://dx.doi.org/10.1007/978-1-4612-0635-4
http://cds.cern.ch/record/2006126
work_keys_str_mv AT gasarchwilliami boundedqueriesinrecursiontheory
AT martingeorgiaa boundedqueriesinrecursiontheory