Bounded Queries in Recursion Theory

by Georgia Martin and William Gasarch

Book Overview

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...

• Format: Hardcover
• Language: English
• ISBN: 0817639667
• ISBN13: 9780817639662
• Release Date: December 1998
• Publisher: Birkhauser
• Length: 353 Pages
• Weight: 1.55 lbs.
• Dimensions: 0.9" x 6.1" x 9.2"