Complexity in Information Theory

ابزارها و اهداف نظریه اطلاعات و پیچیدگی محاسباتی در دهه گذشته به طور قابل توجهی نزدیک‌تر شده‌اند. ابزارهای تحلیلی رایج، مانند ریاضیات ترکیبی و استدلال های جریان اطلاعات، سنگ بنای پیچیدگی VLSl و محاسبات مشارکتی بوده اند. فرض اساسی منابع محاسباتی محدود، مقدمه ای برای رمزنگاری است، جایی که تمایز بین اطلاعات موجود و اطلاعات در دسترس است. نمونه‌های متعدد دیگری از اهداف و ابزارهای مشترک بین این دو رشته، دسته‌بندی تحقیقاتی جدیدی از «نظریه اطلاعات و پیچیدگی» را شکل داده‌اند. این جلد قصد دارد تا برخی از موضوعات مهم اخیر در امتداد این موضوع را در معرض جامعه پژوهشی قرار دهد. مشارکت‌هایی که در اینجا انتخاب شده‌اند، همگی بسیار اساسی، در حال حاضر فعال، نسبتاً تثبیت‌شده و محرک برای پیگیری‌های اساسی هستند. این یک دایره المعارف در مورد این موضوع نیست، بلکه فقط به مشارکت های به موقع با انسجام و وعده کافی می پردازد. سبک های شش فصل طیف وسیعی از نتایج ریاضی خاص تا بررسی مناطق بزرگ را پوشش می دهد. امید است محتوای فنی و مضمون این جلد به ایجاد این حوزه کلی پژوهشی کمک کند. مایلم از نویسندگان فصول برای کمک به این جلد تشکر کنم. همچنین می‌خواهم از اد پوسنر برای ابتکارش برای پرداختن به این موضوع به طور سیستماتیک، و اندی فایف و روث ارلانسون برای تصحیح برخی از فصل‌ها تشکر کنم.

The means and ends of information theory and computational complexity have grown significantly closer over the past decade. Common analytic tools, such as combinatorial mathematics and information flow arguments, have been the cornerstone of VLSl complexity and cooperative computation. The basic assumption of limited computing resources is the premise for cryptography, where the distinction is made between available information and accessible information. Numerous other examples of common goals and tools between the two disciplines have shaped a new research category of 'information and complexity theory'. This volume is intended to expose to the research community some of the recent significant topics along this theme. The contributions selected here are all very basic, presently active, fairly well-established, and stimulating for substantial follow-ups. This is not an encyclopedia on the subject, it is concerned only with timely contributions of sufficient coherence and promise. The styles of the six chapters cover a wide spectrum from specific mathematical results to surveys of large areas. It is hoped that the technical content and theme of this volume will help establish this general research area. I would like to thank the authors of the chapters for contributing to this volume. I also would like to thank Ed Posner for his initiative to address this subject systematically, and Andy Fyfe and Ruth Erlanson for proofreading some of the chapters.