| Record ID | marc_columbia/Columbia-extract-20221130-007.mrc:86291109:4019 |
| Source | marc_columbia |
| Download Link | /show-records/marc_columbia/Columbia-extract-20221130-007.mrc:86291109:4019?format=raw |
LEADER: 04019mam a22004214a 4500
001 3068860
005 20221019211844.0
008 001102t20012001nyua b 001 0 eng
010 $a 00053829
020 $a0387950559 (alk. paper)
035 $a(OCoLC)ocm45315542
035 $9ATP1365CU
035 $a(NNC)3068860
035 $a3068860
040 $aDLC$cDLC$dC#P$dOHX$dOrLoB-B
042 $apcc
050 00 $aQA76$b.H6236 2001
072 7 $aQA$2lcco
082 00 $a004$221
100 1 $aHomer, S.$q(Steven)$0http://id.loc.gov/authorities/names/n90647743
245 10 $aComputability and complexity theory /$cSteven Homer, Alan L. Selman.
260 $aNew York :$bSpringer,$c[2001], ©2001.
300 $axiii, 194 pages :$billustrations ;$c24 cm.
336 $atext$btxt$2rdacontent
337 $aunmediated$bn$2rdamedia
490 1 $aTexts in computer science
504 $aIncludes bibliographical references (p. [181]-185) and indexes.
505 00 $g1.$tPreliminaries.$g1.1.$tWords and Languages.$g1.2.$tK-adic Representation.$g1.3.$tPartial Functions.$g1.4.$tGraphs.$g1.5.$tPropositional Logic.$g1.6.$tCardinality.$g1.7.$tElementary Algebra --$g2.$tIntroduction to Computability.$g2.1.$tTuring Machines.$g2.2.$tTuring-Machine Concepts.$g2.3.$tVariations of Turing Machines.$g2.4.$tChurch's Thesis.$g2.5.$tRAMs --$g3.$tUndecidability.$g3.1.$tDecision Problems.$g3.2.$tUndecidable Problems.$g3.3.$tPairing Functions.$g3.4.$tComputably Enumerable Sets.$g3.5.$tHalting Problem, Reductions, and Complete Sets.$g3.6.$tS-m-n Theorem.$g3.7.$tRecursion Theorem.$g3.8.$tRice's Theorem.$g3.9.$tTuring Reductions and Oracle Turing Machines.$g3.10.$tRecursion Theorem, Continued --$g4.$tIntroduction to Complexity Theory.$g4.1.$tComplexity Classes and Complexity Measures.$g4.2.$tPrerequisites --$g5.$tBasic Results of Complexity Theory.$g5.1.$tLinear Compression and Speedup.$g5.2.$tConstructible Functions.$g5.3.$tTape Reduction.$g5.4.$tInclusion Relationships.
505 80 $g5.5.$tSeparation Results.$g5.6.$tTranslation Techniques and Padding.$g5.7.$tRelations between the Standard Classes - Continued --$g6.$tNondeterminism and NP-Completeness.$g6.1.$tCharacterizing NP.$g6.2.$tThe Class P.$g6.3.$tEnumerations.$g6.4.$tNP-Completeness.$g6.5.$tThe Cook-Levin Theorem.$g6.6.$tMore NP-Complete Problems --$g7.$tRelative Computability.$g7.1.$tNP-Hardness.$g7.2.$tSearch Problems.$g7.3.$tThe Structure of NP.$g7.4.$tThe Polynomial Hierarchy.$g7.5.$tComplete Problems for Other Complexity Classes.
520 1 $a"The theory of computing provides computer science with concepts, models, and formalisms for reasoning about the resources needed to carry out computations and about the efficiency of the computations that use these resources. In addition, it provides tools to measure the difficulty of combinatorial problems both absolutely and in comparison with other problems.".
520 8 $a"Requiring no explicit prerequisite knowledge, Computability and Complexity Theory introduces materials that are the core knowledge in the theory of computation. The book is self-contained, with a preliminary chapter describing key mathematical concepts and notations and subsequent chapters moving from the qualitative aspects of classical computability theory to the quantitative aspects of complexity theory.
520 8 $aDedicated chapters on undecidability NP-completeness and relative computability round of the work, which focuses on the limitations of computability and the distinctions between feasible and intractable."--BOOK JACKET.
650 0 $aComputer science.$0http://id.loc.gov/authorities/subjects/sh89003285
650 0 $aComputable functions.$0http://id.loc.gov/authorities/subjects/sh85029469
650 0 $aComputational complexity.$0http://id.loc.gov/authorities/subjects/sh85029473
700 1 $aSelman, Alan L.$0http://id.loc.gov/authorities/names/n85269968
830 0 $aTexts in computer science.$0http://id.loc.gov/authorities/names/n2005047943
852 00 $boff,eng$hQA76$i.H6236 2001