نام کتاب: Communication Complexity – A New Approach To Circuit Depth
نویسنده: Mauricio Karchmer
ویرایش: ۱
سال انتشار: ۱۹۸۹
کد ISBN کتاب: ۰۲۶۲۱۱۱۴۳۸, ۹۷۸۰۲۶۲۱۱۱۴۳۰
فرمت: PDF
تعداد صفحه: ۸۶
انتشارات: The Mit Press
Description About Book Communication Complexity – A New Approach To Circuit Depth From Amazon
Communication Complexity describes a new intuitive model for studying circuit networks that captures the essence of circuit depth. Although the complexity of boolean functions has been studied for almost 4 decades, the main problems the inability to show a separation of any two classes, or to obtain nontrivial lower bounds remain unsolved. The communication complexity approach provides clues as to where to took for the heart of complexity and also sheds light on how to get around the difficulty of proving lower bounds. Karchmer’s approach looks at a computation device as one that separates the words of a language from the non-words. It views computation in a top down fashion, making explicit the idea that flow of information is a crucial term for understanding computation. Within this new setting, Communication Complexity gives simpler proofs to old results and demonstrates the usefulness of the approach by presenting a depth lower bound for st-connectivity. Karchmer concludes by proposing open problems which point toward proving a general depth lower bound. Mauricio Karchmer received his doctorate from Hebrew University and is currently a Postdoctoral Fellow at the University of Toronto. Communication Complexity received the 1988 ACM Doctoral Dissertation Award.
درباره کتاب Communication Complexity – A New Approach To Circuit Depth ترجمه شده از گوگل
ارتباطات پیچیدگی توصیف یک مدل بصری جدیدی را برای مطالعه شبکه های مدار که قطاری از جوهر از عمق مدار است. اگرچه پیچیدگی توابع بولی است برای تقریبا ۴ دهه مورد بررسی است، مشکلات اصلی ناتوانی برای نشان دادن یک جدایی هر دو طبقه، و یا برای به دست آوردن کوچک اما با اهمیت کران پایین حل نشده باقی مانده است. رویکرد پیچیدگی ارتباطات سرنخ فراهم می کند به عنوان جایی که برای قلب پیچیدگی گرفت و همچنین به مسائلی در مورد چگونگی گرفتن سراسر دشواری اثبات کران پایین. به نظر می رسد رویکرد Karchmer در یک دستگاه محاسبات به عنوان یکی که کلمات از یک زبان از غیر کلمات جدا می کند. نمایش ها محاسبات در بالا به پایین مد، ساخت به صراحت این ایده که از جریان اطلاعات یک اصطلاح بسیار مهم برای درک محاسبات است. در این محیط جدید، ارتباطات پیچیدگی می دهد مدرک ساده تر به نتایج قدیمی و نشان می دهد که سودمندی این رویکرد با ارائه عمق کمتری برای ST-اتصال محدود شده است. Karchmer نتیجه با پیشنهاد مشکلات باز که در آن نقطه به سمت اثبات عمق کلی پایین تر. موریسیو Karchmer دکترای خود را از دانشگاه عبری دریافت کرد و در حال حاضر محقق فوق دکترا در دانشگاه تورنتو. ارتباطات پیچیدگی جایزه بهترین رساله دکتری ACM 1988 دریافت کرده است.
[box type=”info”]
جهت دسترسی به توضیحات این کتاب در Amazon اینجا کلیک کنید.
در صورت خراب بودن لینک کتاب، در قسمت نظرات همین مطلب گزارش دهید.
با خرید اشتراک، بدون محدودیت، کتاب دانلود کن!
