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

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

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

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

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 probabilisticalgorithms, 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.