Год издания: 2004
Количество страниц: 352
В продаже с 18.01.2012
Как только цена на книгу Computational Complexity: A Quantitative Perspective, Volume 196 (North-Holland Mathematics Studies) в одном из интернет-магазинов упадет ниже указанной Вами, Вам на e-mail будет отправлено уведомление.Укажите e-mail для связи: Укажите ожидаемую цену:
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....