مدارهای بولی و پیچیدگی مدار

مدارهای بولی توابع را از طریق شبکه‌های گیت‌های منطقی محاسبه می‌کنند و پیچیدگی مدار، مسائل را بر اساس اندازه و عمق مدارهای مورد نیاز برای حل آن‌ها اندازه‌گیری می‌کند و دیدگاهی موازی و سخت‌افزاری از محاسبات ارائه می‌دهد.

Definition

مدار بولی یک گراف جهت‌دار بدون دور از گیت‌های منطقی است که تابعی از ورودی‌های باینری با طول ثابت را محاسبه می‌کند؛ پیچیدگی مدار حداقل تعداد گیت‌ها، عمق یا سایر منابع ساختاری مورد نیاز برای محاسبه یک خانواده معین از توابع بولی را مطالعه می‌کند.

Scope

این موضوع مدارهای بولی و فرمول‌ها، معیارهای اندازه و عمق پیچیدگی، مدل‌های یکنواخت در مقابل غیریکنواخت، کلاس‌های عمق کم مانند NC و AC، رابطه بین کران‌های پایین مدار و جداسازی کلاس‌های پیچیدگی، و نتایج برجسته کران پایین برای خانواده‌های مدار محدود را پوشش می‌دهد.

Core questions

• دیدگاه شبکه گیت‌ها در محاسبات چه تفاوتی با ماشین‌های ترتیبی دارد؟
• اندازه و عمق مدار چه چیزی را اندازه‌گیری می‌کنند و چگونه با زمان و موازی‌سازی مرتبط هستند؟
• چرا کران‌های پایین مدار مسیری برای جداسازی کلاس‌های پیچیدگی هستند؟
• چه کران‌های پایینی شناخته شده‌اند و چه موانعی از کران‌های قوی‌تر جلوگیری می‌کنند؟

Key theories

ناهمگونی و کلاس P/poly

مدارها امکان استفاده از ماشین‌های مختلف برای هر طول ورودی را فراهم می‌کنند و کلاس ناهمگون P/poly را ایجاد می‌کنند که شامل P است؛ نشان دادن اینکه یک مسئله NP-کامل فاقد مدارهای با اندازه چندجمله‌ای است، P را از NP جدا می‌کند و به کران‌های پایین مدار انگیزه می‌دهد.

کران‌های پایین برای مدارهای محدود

کران‌های پایین قوی برای خانواده‌های محدود شناخته شده‌اند، مانند اندازه نمایی مورد نیاز برای مدارهای با عمق ثابت که توازن را محاسبه می‌کنند، حتی اگر کران‌های پایین برای مدارهای عمومی همچنان دور از دسترس باشند.

Clinical relevance

مدارها مدل طبیعی سخت‌افزار دیجیتال هستند، بنابراین پیچیدگی مدار طراحی تراشه و محدودیت‌های محاسبات موازی را مشخص می‌کند؛ کلاس‌های عمق کم آنچه را که می‌توان به سرعت با پردازنده‌های زیاد محاسبه کرد، نشان می‌دهند و کران‌های پایین مدار یک استراتژی اصلی در تلاش بلندمدت برای حل مسائلی مانند P در مقابل NP هستند.

History

شانون در سال ۱۹۳۷ جبر بولی را به مدارهای سوئیچینگ مرتبط کرد و پیچیدگی مدار به عنوان یک رشته در دهه ۱۹۸۰ زمانی که فرست، ساکس، سیپسر و دیگران کران‌های پایین عمق ثابت را برای توازن اثبات کردند، و رازبوروف و اسمولنسکی روش‌های جبری را توسعه دادند، قبل از اینکه مانع اثبات‌های طبیعی نشان دهد که چرا کران‌های پایین عمومی اینقدر گریزان هستند، به بلوغ رسید.

Key figures

• Claude Shannon
• Alexander Razborov
• Andrew Yao
• Roman Smolensky

Seminal works

• aroraBarak2009
• vollmer1999

Frequently asked questions

مدارها چه تفاوتی با ماشین‌های تورینگ دارند؟

ماشین تورینگ یک دستگاه واحد است که ورودی‌هایی با هر اندازه را گام به گام پردازش می‌کند، در حالی که مدار یک شبکه ثابت از گیت‌ها برای یک طول ورودی است، با یک مدار جداگانه برای هر طول. این ناهمگونی مدارها را به یک مدل طبیعی از سخت‌افزار و محاسبات موازی تبدیل می‌کند و می‌تواند چیزهایی را بیان کند که هیچ ماشین یکنواخت واحدی نمی‌تواند.

چرا محققان به کران‌های پایین مدار اهمیت می‌دهند؟

اثبات اینکه یک مسئله در NP به مدارهای بسیار بزرگ نیاز دارد، کلاس‌های پیچیدگی را جدا می‌کند و می‌تواند P در مقابل NP را حل کند. کران‌های پایین برای خانواده‌های مدار محدود شناخته شده‌اند، اما گسترش آن‌ها به مدارهای عمومی توسط موانع رسمی مسدود شده است، که این را به یکی از عمیق‌ترین چالش‌های حل نشده در این زمینه تبدیل می‌کند.