دانلود کتاب Computational Complexity: A Quantitative Perspective

ترجمه فارسی توضیحات (ترجمه ماشینی)

پیچیدگی محاسباتی: دیدگاه کمی

تصور رایجی وجود دارد که پیچیدگی محاسباتی یک نظریه “اخبار بد” است، زیرا معمول ترین نتایج آن ادعا می کند که کارهای مختلف در دنیای واقعی و بی گناه غیرممکن هستند. در واقع، «اخبار بد» یک اصطلاح نسبی است، و در واقع، در برخی موقعیت‌ها (مثلاً در رمزنگاری)، ما می‌خواهیم دشمن نتواند وظیفه خاصی را انجام دهد. با این حال، یک نتیجه “خبر بد” به طور خودکار در چنین سناریویی مفید نمی شود. برای اینکه این اتفاق بیفتد، ویژگی های سختی آن باید به صورت کمی ارزیابی شود و نشان داده شود که به طور گسترده آشکار می شود. این کتاب تجزیه و تحلیل کمی از برخی از نتایج اصلی در پیچیدگی را انجام می‌دهد که به دسته‌هایی از مسائل یا مشکلات مشخص فردی مربوط می‌شوند. اندازه برخی از کلاس های مهم با استفاده از ابزارهای توپولوژیکی و اندازه گیری-نظری محدود به منابع مورد مطالعه قرار می گیرد. در مورد مشکلات فردی، این کتاب ویژگی‌های کمی مرتبط مانند خواص تقریبی یا تعداد ورودی‌های سخت در هر طول را مطالعه می‌کند. یک فصل به نظریه پیچیدگی انتزاعی اختصاص داده شده است، یک زمینه قدیمی تر که با این حال، شایستگی توجه را دارد زیرا پایه های پیچیدگی را بیان می کند. از سوی دیگر، فصول دیگر بر تحولات اخیر و مهم در پیچیدگی تمرکز دارند. این کتاب به شیوه ای نسبتاً دقیق مفاهیمی را ارائه می دهد که در دهه گذشته یا بیشتر در مرکز خطوط اصلی تحقیقاتی در پیچیدگی قرار داشته اند، مانند: میانگین پیچیدگی، محاسبات کوانتومی، تقویت سختی، اندازه گیری محدود به منابع، رابطه بین توابع یک طرفه و مولدهای شبه تصادفی، رابطه بین محمولات سخت و مولدهای شبه تصادفی، استخراج‌کننده‌ها، غیر تصادفی‌سازی الگوریتم‌های احتمالی خطای محدود، اثبات‌های احتمالی قابل بررسی، عدم تقریب‌پذیری مسائل بهینه‌سازی و موارد دیگر. این کتاب باید برای دانشجویان فارغ التحصیل علوم کامپیوتر، و محققانی که به نظریه علوم کامپیوتر علاقه دارند و به درک خوبی از پیچیدگی محاسباتی نیاز دارند، به عنوان مثال، محققان در الگوریتم‌ها، هوش مصنوعی، منطق و سایر رشته‌ها جذاب باشد. Â · تأکید بر ویژگی های کمی مربوط به نتایج مهم در پیچیدگی است. Â · پوشش مستقل و قابل دسترسی برای مخاطبان گسترده است. طیف وسیعی از موضوعات مهم از جمله: تکنیک های تصادفی سازی، عدم تقریب مسایل بهینه سازی، پیچیدگی حالت متوسط، محاسبات کوانتومی، توابع یک طرفه و مولدهای شبه تصادفی، اندازه گیری محدود به منابع و توپولوژی.

Computational Complexity: A Quantitative Perspective

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. One chapter is dedicated to abstract complexity theory, an older field which, however, deserves attention because it lays out the foundations of complexity. The other chapters, on the other hand, focus on recent and important developments in complexity. The book presents in a fairly detailed manner concepts that have been at the centre of the main research lines in complexity in the last decade or so, such as: average-complexity, quantum computation, hardness amplification, resource-bounded measure, the relation between one-way functions and pseudo-random generators, the relation between hard predicates and pseudo-random generators, extractors, derandomization of bounded-error probabilistic algorithms, probabilistically checkable proofs, non-approximability of optimization problems, and others. The book should appeal to graduate computer science students, and to researchers who have an interest in computer science theory and need a good understanding of computational complexity, e.g., researchers in algorithms, AI, logic, and other disciplines. · Emphasis is on relevant quantitative attributes of important results in complexity. · Coverage is self-contained and accessible to a wide audience. · Large range of important topics including: derandomization techniques, non-approximability of optimization problems, average-case complexity, quantum computation, one-way functions and pseudo-random generators, resource-bounded measure and topology.