| Bounded Queries in Recursion Theory 1999 Edition Contributor(s): Levine, William (Author), Martin, Georgia (Author) |
|
 |
ISBN: 0817639667 ISBN-13: 9780817639662 Publisher: Birkhauser OUR PRICE: $104.49 Product Type: Hardcover - Other Formats Published: December 1998 |
| Additional Information |
| BISAC Categories: - Computers | Machine Theory - Computers | Data Processing - Mathematics | Functional Analysis |
| Dewey: 004.015 |
| LCCN: 98046023 |
| Series: Progress in Computer Science and Applied Logic |
| Physical Information: 0.88" H x 6.14" W x 9.21" (1.55 lbs) 353 pages |
| Descriptions, Reviews, Etc. |
| Publisher 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. |