موضوع مقاله: پیچیدگی مدار | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # پیچیدگی مدار | مقدمه: در علوم نظری رایانه، پیچیدگی مدار شاخه‌ای از نظریه پیچیدگی محاسباتی است که در آن توابع بولی بر اساس اندازه یا عمق مدارهای بولی که آن‌ها را محاسبه می‌کنند، دسته‌بندی می‌شوند. | ## بخش 1: پیچیدگی مدار | مفهومی مرتبط با این موضوع، پیچیدگی مدار یک زبان بازگشتی است که توسط یک خانواده یکنواخت از مدارها تصمیم‌گیری می‌شود اثبات کران‌های پایین برای اندازه مدارهای بولی که توابع بولی مشخصی را محاسبه می‌کنند، یک روش محبوب برای جداسازی کلاس‌های پیچیدگی است. به‌عنوان مثال، یک کلاس مدار برجسته به نام P/poly شامل توابع بولی است که توسط مدارهایی با اندازه چندجمله‌ای قابل محاسبه هستند. اثبات اینکه می‌تواند کلاس‌های P و NP را از هم جدا کند (نگاه کنید به ادامه مطلب) کلاس‌های پیچیدگی که بر اساس مدارهای بولی تعریف می‌شوند، شامل و AC0, AC, TC0, NC1, NC هستند . اندازه و عمق یک مدار بولی با بیت ورودی یک گراف جهت‌دار بدون دور است که در آن هر گره (که در این زمینه معمولاً به آن‌ها گیت گفته می‌شود) یکی از موارد زیر است یک گره ورودی با درجه ورودی صفر که با یکی از بیت ورودی برچسب‌گذاری شده است ، یک گیت AND ، یک گیت OR ، یا یک گیت NOT . اندازه مدار برابر است با تعداد گیت‌های موجود در آن و عمق مدار برابر است با طول بیشینه یک مسیر از یک گره ورودی به گیت خروجی . پیچیدگی اندازه مدار برای یک تابع بولی برابر است با کوچک‌ترین اندازه مداری که می‌تواند را محاسبه کند . پیچیدگی عمق مدار برای یک تابع بولی برابر است با کمینه عمق مداری که می‌تواند را محاسبه کند . این مفاهیم زمانی تعمیم می‌یابند که پیچیدگی مدار را برای یک زبان به‌ویژه زبان‌های رسمی بی‌نهایت در نظر بگیریم که شامل رشته‌هایی با طول بیت‌های متفاوت است. بنابراین، هیچ مدار بولی واحدی قادر به تصمیم‌گیری درباره یک زبان با طول‌های متغیر نیست . | ## بخش 2: پیچیدگی مدار | برای حل این مشکل، خانواده‌ای از مدارها در نظر گرفته می‌شود که در آن هر مدار ورودی‌هایی با اندازه را می‌پذیرد . هر خانواده مدار به طور طبیعی یک زبان را تولید می‌کند، به این صورت که مدار خروجی ۱ را زمانی تولید می‌کند که یک رشته با طول عضو آن زبان باشد و در غیر این صورت خروجی ۰ می‌دهد . خانواده‌ای از مدارها حداقل اندازه دارد اگر هیچ خانواده دیگری وجود نداشته باشد که بتواند با مدارهایی با اندازه کوچک‌تر نسبت به برای هر اندازه ورودی‌ها تصمیم‌گیری کند (و همین‌طور برای خانواده‌هایی که حداقل عمق دارند) . بنابراین، پیچیدگی مدار حتی برای زبان‌های غیر بازگشتی نیز معنادار است .مفهوم یک خانواده یکنواخت امکان ارتباط بین پیچیدگی مدار و معیارهای پیچیدگی مبتنی بر الگوریتم برای زبان‌های بازگشتی را فراهم می‌کند. اما، نوع غیر یکنواخت در یافتن کران‌های پایین برای میزان پیچیدگی مورد نیاز هر خانواده مدار برای تصمیم‌گیری درباره زبان‌های معین مفید است .تعریف رسمی پیچیدگی مدار یچیدگی اندازه مدار یک زبان رسمی به صورت تابعی تعریف می‌شود که طول بیت ورودی را به پیچیدگی اندازه مدار حداقل نسبت می‌دهد . یکنواختی مدارهای بولی یکی از نمونه‌های برجسته مدل‌های محاسباتی غیر یکنواخت هستند، به این معنی که ورودی‌های با طول‌های مختلف توسط مدارهای مختلف پردازش می‌شوند، برخلاف مدل‌های یکنواخت مانند ماشین‌های تورینگ که همان دستگاه محاسباتی برای تمام طول‌های ورودی ممکن استفاده می‌شود. یک مساله محاسباتی خاص با یک خانواده خاص از مدارهای بولی مرتبط است که در آن هر مدار ورودی‌هایی با n بیت را پردازش می‌کند . زمانی که زمان اجرای این ماشین تورینگ چندجمله‌ای در باشد، خانواده مدارها به عنوان P _ یکنواخت شناخته می شود.شرط سخت‌گیرانه‌تر یکنواختی DLOGTIME _ یکنواخت کاربرد خاصی در مطالعه کلاس های کم عمق مدار همچون AC*0 یا TC*0 دارد . یکنواختی زمان چندجمله‌ای یک خانواده مدارهای بولی یکنواخت زمان چندجمله‌ای است اگر یک ماشین تورینگ قطعی M وجود داشته باشد به طوری که M در زمان چندجمله‌ای اجرا می‌شود برای همه ، توضیح مدار را بر روی ورودی تولید می‌کند . | ## بخش 3: پیچیدگی مدار | یکنواختی فضای لگاریتمی یک خانواده مدارهای بولی یکنواخت فضای لگاریتمی است اگر یک ماشین تورینگ قطعی M وجود داشته باشد به طوری که M در فضای کاری لگاریتمی اجرا می‌شود (یعنی یک ترانسدیوسر فضای لگاریتمی است) برای همه ، M توضیح مدار را بر روی ورودی تولید می‌کند. تاریخچه پیچیدگی مدار به سال 1949 برمی‌گردد، زمانی که شانون ثابت کرد که تقریباً تمام توابع بولی بر روی n متغیر به مدارهایی با اندازه Θ(2n/n) نیاز دارند . با وجود این حقیقت، نظریه‌پردازان پیچیدگی تاکنون نتوانسته‌اند یک کران پایین فوق‌خطی برای هیچ تابع مشخص اثبات کنند . کران‌های پایین فوق‌چندجمله‌ای تحت شرایط خاصی برای خانواده مدارهای استفاده‌شده اثبات شده است .اولین تابعی که برای آن کران پایین فوق‌چندجمله‌ای مدارها نشان داده شد، تابع زوجیت است که مجموع بیت‌های ورودی خود را بر حسب مدول ۲ محاسبه می‌کند.. این واقعیت که تابع زوجیت در AC0 وجود ندارد، اولین‌بار به طور مستقل توسط آجتای در 1983 و توسط فرست، ساکس و سیپسر در 1984 اثبات شد . بهبودهای بعدی توسط هاستاد در 1987 نشان داد که هر خانواده‌ای از مدارهای با عمق ثابت که تابع زوجیت را محاسبه می‌کنند، به اندازه نمایی نیاز دارند. با گسترش نتیجه‌ای از رازبوروف، اسمولنسکی در 1987 اثبات کرد که این امر حتی در صورتی که مدار با گیت‌هایی که مجموع بیت‌های ورودی را بر حسب مدول یک عدد اول فرد p محاسبه می‌کنند، گسترش یابد، نیز درست است . برای هر انتخاب خاص از ثابت های n و k گراف می تواند به صورت دودویی کدگذاری شود با استفاده از و این خانواده از توابع ، تک تن است و می توان آن را توسط خانواده ای از مدار ها محاسبه کرد ، اما نشان داده شده است که نمی توان ان را با خانواده ای از مدار های تک تن با اندازه چند جمله ای محاسبه کرد . نتیجه اصلی رازباروف در سال 1987 توسط آلن و بوپانو به یک کران پایین نمایی بهبود یافت . | ## جمع‌بندی | در سال 2008 راسمن نشان داد که مدار های عمق ثابت با دروازه های OR ، AND ، NOT برای حل مساله حتی در حالت متوسط استفاده شده .