پیچیدگی مدار کیست؟ توضیح بده.
در علوم نظری رایانه، پیچیدگی مدار شاخه‌ای از نظریه پیچیدگی محاسباتی است که در آن توابع بولی بر اساس اندازه یا عمق مدارهای بولی که آن‌ها را محاسبه می‌کنند، دسته‌بندی می‌شوند. مفهومی مرتبط با این موضوع، پیچیدگی مدار یک زبان بازگشتی است که توسط یک خانواده یکنواخت از مدارها تصمیم‌گیری می‌شود formula_1اثبات کران‌های پایین برای اندازه مدارهای بولی که توابع بولی مشخصی را محاسبه می‌کنند، یک روش محبوب برای جداسازی کلاس‌های پیچیدگی است. به‌عنوان مثال، یک کلاس مدار برجسته به نام P/poly شامل توابع بولی است که توسط مدارهایی با اندازه چندجمله‌ای قابل محاسبه هستند. اثبات اینکه formula_2می‌تواند کلاس‌های P و NP را از هم جدا کند (نگاه کنید به ادامه مطلب)کلاس‌های پیچیدگی که بر اساس مدارهای بولی تعریف می‌شوند، شامل و AC0, AC, TC0, NC1, NC هستند .= اندازه و عمق =یک مدار بولی با formula_3 بیت ورودی یک گراف جهت‌دار بدون دور است که در آن هر گره (که در این زمینه معمولاً به آن‌ها گیت گفته می‌شود) یکی از موارد زیر است یک گره ورودی با درجه ورودی صفر که با یکی از formula_3 بیت ورودی برچسب‌گذاری شده است ، یک گیت AND ، یک گیت OR ، یا یک گیت NOT . یکی از این گیت‌ها به‌عنوان گیت خروجی تعیین می‌شود . چنین مداری به طور طبیعی یک تابع از formula_3 ورودی‌های خود را محاسبه می‌کند . اندازه مدار برابر است با تعداد گیت‌های موجود در آن و عمق مدار برابر است با طول بیشینه یک مسیر از یک گره ورودی به گیت خروجی . دو مفهوم اصلی پیچیدگی مدار موجودند . پیچیدگی اندازه مدار برای یک تابع بولی formula_6برابر است با کوچک‌ترین اندازه مداری که می‌تواند را محاسبه کند . پیچیدگی عمق مدار برای یک تابع بولی formula_6 برابر است با کمینه عمق مداری که می‌تواند formula_6 را محاسبه کند .این مفاهیم زمانی تعمیم می‌یابند که پیچیدگی مدار را برای یک زبان به‌ویژه زبان‌های رسمی بی‌نهایت در نظر بگیریم که شامل رشته‌هایی با طول بیت‌های متفاوت است. با این حال، مدارهای بولی تنها تعداد ثابتی از بیت‌های ورودی را می‌پذیرند. بنابراین، هیچ مدار بولی واحدی قادر به تصمیم‌گیری درباره یک زبان با طول‌های متغیر نیست . برای حل این مشکل، خانواده‌ای از مدارها formula_9 در نظر گرفته می‌شود که در آن هر مدار formula_10 ورودی‌هایی با اندازه formula_3 را می‌پذیرد . هر خانواده مدار به طور طبیعی یک زبان را تولید می‌کند، به این صورت که مدار formula_12 خروجی ۱ را زمانی تولید می‌کند که یک رشته با طول عضو آن زبان باشد و در غیر این صورت خروجی ۰ می‌دهد . خانواده‌ای از مدارها حداقل اندازه دارد اگر هیچ خانواده دیگری وجود نداشته باشد که بتواند با مدارهایی با اندازه کوچک‌تر نسبت به formula_10 برای هر اندازه formula_3 ورودی‌ها تصمیم‌گیری کند (و همین‌طور برای خانواده‌هایی که حداقل عمق دارند) . بنابراین، پیچیدگی مدار حتی برای زبان‌های غیر بازگشتی نیز معنادار است .مفهوم یک خانواده یکنواخت امکان ارتباط بین پیچیدگی مدار و معیارهای پیچیدگی مبتنی بر الگوریتم برای زبان‌های بازگشتی را فراهم می‌کند. اما، نوع غیر یکنواخت در یافتن کران‌های پایین برای میزان پیچیدگی مورد نیاز هر خانواده مدار برای تصمیم‌گیری درباره زبان‌های معین مفید است .تعریف رسمی پیچیدگی مدار یچیدگی اندازه مدار یک زبان رسمی formula_15 به صورت تابعی formula_16 تعریف می‌شود که طول بیت ورودی formula_3 را به پیچیدگی اندازه مدار حداقل formula_12 نسبت می‌دهد . این مدار تصمیم می‌گیرد که آیا ورودی‌هایی با این طول عضو هستند یا خیر. پیچیدگی عمق مدار نیز به طور مشابه تعریف می‌شود .= یکنواختی =مدارهای بولی یکی از نمونه‌های برجسته مدل‌های محاسباتی غیر یکنواخت هستند، به این معنی که ورودی‌های با طول‌های مختلف توسط مدارهای مختلف پردازش می‌شوند، برخلاف مدل‌های یکنواخت مانند ماشین‌های تورینگ که همان دستگاه محاسباتی برای تمام طول‌های ورودی ممکن استفاده می‌شود. یک مساله محاسباتی خاص با یک خانواده خاص از مدارهای بولی formula_19 مرتبط است که در آن هر مدار formula_10 ورودی‌هایی با n بیت را پردازش می‌کند . . معمولاً یک شرط یکنواختی بر روی این خانواده‌ها اعمال می‌شود که وجود یک ماشین تورینگ با محدودیت منابع را می‌طلبد که برای ورودی n توضیحی از مدار فردی formula_10 را تولید کند . زمانی که زمان اجرای این ماشین تورینگ چندجمله‌ای در باشد، خانواده مدارها به عنوان P _ یکنواخت شناخته می شود.شرط سخت‌گیرانه‌تر یکنواختی DLOGTIME _ یکنواخت کاربرد خاصی در مطالعه کلاس های کم عمق مدار همچون AC*0 یا TC*0 دارد . زمانی که هیچ محدودیت منابعی مشخص نشود، یک زبان بازگشتی است (یعنی قابل تصمیم‌گیری توسط یک ماشین تورینگ) اگر و تنها اگر زبان توسط یک خانواده یکنواخت از مدارهای بولی تصمیم‌گیری شود .یکنواختی زمان چندجمله‌ای.یک خانواده مدارهای بولی formula_22 یکنواخت زمان چندجمله‌ای است اگر یک ماشین تورینگ قطعی M وجود داشته باشد به طوری که یکنواختی فضای لگاریتمی.یک خانواده مدارهای بولی formula_22 یکنواخت فضای لگاریتمی است اگر یک ماشین تورینگ قطعی M وجود داشته باشد به طوری که= تاریخچه =پیچیدگی مدار به سال 1949 برمی‌گردد، زمانی که شانون ثابت کرد که تقریباً تمام توابع بولی بر روی "n" متغیر به مدارهایی با اندازه Θ(2"n"/"n") نیاز دارند . با وجود این حقیقت، نظریه‌پردازان پیچیدگی تاکنون نتوانسته‌اند یک کران پایین فوق‌خطی برای هیچ تابع مشخص اثبات کنند . کران‌های پایین فوق‌چندجمله‌ای تحت شرایط خاصی برای خانواده مدارهای استفاده‌شده اثبات شده است .اولین تابعی که برای آن کران پایین فوق‌چندجمله‌ای مدارها نشان داده شد، تابع زوجیت است که مجموع بیت‌های ورودی خود را بر حسب مدول ۲ محاسبه می‌کند.. این واقعیت که تابع زوجیت در AC0 وجود ندارد، اولین‌بار به طور مستقل توسط آجتای در 1983 و توسط فرست، ساکس و سیپسر در 1984 اثبات شد . بهبودهای بعدی توسط هاستاد در 1987 نشان داد که هر خانواده‌ای از مدارهای با عمق ثابت که تابع زوجیت را محاسبه می‌کنند، به اندازه نمایی نیاز دارند. با گسترش نتیجه‌ای از رازبوروف، اسمولنسکی در 1987 اثبات کرد که این امر حتی در صورتی که مدار با گیت‌هایی که مجموع بیت‌های ورودی را بر حسب مدول یک عدد اول فرد "p" محاسبه می‌کنند، گسترش یابد، نیز درست است . "مساله k"-clique این است که مشخص کنیم آیا یک گراف داده شده با n راس ، کلیکی به اندازه k دارد یا نه . برای هر انتخاب خاص از ثابت های n و k گراف می تواند به صورت دودویی کدگذاری شود با استفاده از formula_30 و formula_31 این خانواده از توابع ، تک تن است و می توان آن را توسط خانواده ای از مدار ها محاسبه کرد ، اما نشان داده شده است که نمی توان ان را با خانواده ای از مدار های تک تن با اندازه چند جمله ای محاسبه کرد . نتیجه اصلی رازباروف در سال 1987 توسط آلن و بوپانو به یک کران پایین نمایی بهبود یافت . در سال 2008 راسمن نشان داد که مدار های عمق ثابت با دروازه های OR ، AND ، NOT برای حل مساله حتی در حالت متوسط formula_32 استفاده شده . در حالت کلی مداری با اندازه formula_33 نیاز است .