TY  - BOOK
AU  - Zimand, Marius
TI  - Computational complexity: a quantitative perspective 
SN  - 9780444828415
U1  - 511.352 
PY  - 2004///
CY  - Amesterdam
PB  - Elsevier
KW  - Computational complexity
N2  - There has been a common perception that computational complexity is a theory of bad news because its most typical results assert that various real-world and innocent-looking tasks are infeasible. In fact, bad news is a relative term, and, indeed, in some situations (e.g., in cryptography), we want an adversary to not be able to perform a certain task. However, a ""bad news"" result does not automatically become useful in such a scenario. For this to happen, its hardness features have to be quantitatively evaluated and shown to manifest extensively.  The book undertakes a quantitative analysis of some of the major results in complexity that regard either classes of problems or individual concrete problems. The size of some important classes are studied using resource-bounded topological and measure-theoretical tools. In the case of individual problems, the book studies relevant quantitative attributes such as approximation properties or the number of hard inputs at each length
ER  -