پیچیدگی مدار

در علوم نظری رایانه، پیچیدگی مدار شاخه‌ای از نظریه پیچیدگی محاسباتی است که در آن توابع بولی بر اساس اندازه یا عمق مدارهای بولی که آن‌ها را محاسبه می‌کنند، دسته‌بندی می‌شوند. مفهومی مرتبط با این موضوع، پیچیدگی مدار یک زبان بازگشتی است که توسط یک خانواده یکنواخت از مدارها تصمیم‌گیری می‌شود $C_1,C_2,...$

اثبات کران‌های پایین برای اندازه مدارهای بولی که توابع بولی مشخصی را محاسبه می‌کنند، یک روش محبوب برای جداسازی کلاس‌های پیچیدگی است. به‌عنوان مثال، یک کلاس مدار برجسته به نام P/poly شامل توابع بولی است که توسط مدارهایی با اندازه چندجمله‌ای قابل محاسبه هستند. اثبات اینکه $NP⊈P/poly$می‌تواند کلاس‌های P و NP را از هم جدا کند (نگاه کنید به ادامه مطلب)

کلاس‌های پیچیدگی که بر اساس مدارهای بولی تعریف می‌شوند، شامل و AC⁰, AC, TC⁰, NC¹, NC هستند .

اندازه و عمق

یک مدار بولی با $n$ بیت ورودی یک گراف جهت‌دار بدون دور است که در آن هر گره (که در این زمینه معمولاً به آن‌ها گیت گفته می‌شود) یکی از موارد زیر است یک گره ورودی با درجه ورودی صفر که با یکی از $n$ بیت ورودی برچسب‌گذاری شده است ، یک گیت AND ، یک گیت OR ، یا یک گیت NOT . یکی از این گیت‌ها به‌عنوان گیت خروجی تعیین می‌شود . چنین مداری به طور طبیعی یک تابع از $n$ ورودی‌های خود را محاسبه می‌کند . اندازه مدار برابر است با تعداد گیت‌های موجود در آن و عمق مدار برابر است با طول بیشینه یک مسیر از یک گره ورودی به گیت خروجی . دو مفهوم اصلی پیچیدگی مدار موجودند . پیچیدگی اندازه مدار برای یک تابع بولی $f$برابر است با کوچک‌ترین اندازه مداری که می‌تواند  را محاسبه کند . پیچیدگی عمق مدار برای یک تابع بولی $f$ برابر است با کمینه عمق مداری که می‌تواند $f$ را محاسبه کند .

این مفاهیم زمانی تعمیم می‌یابند که پیچیدگی مدار را برای یک زبان به‌ویژه زبان‌های رسمی بی‌نهایت در نظر بگیریم که شامل رشته‌هایی با طول بیت‌های متفاوت است. با این حال، مدارهای بولی تنها تعداد ثابتی از بیت‌های ورودی را می‌پذیرند. بنابراین، هیچ مدار بولی واحدی قادر به تصمیم‌گیری درباره یک زبان با طول‌های متغیر نیست . برای حل این مشکل، خانواده‌ای از مدارها $C_1,C_2,\dots$ در نظر گرفته می‌شود که در آن هر مدار $C_n$ ورودی‌هایی با اندازه $n$ را می‌پذیرد . هر خانواده مدار به طور طبیعی یک زبان را تولید می‌کند، به این صورت که مدار $C_n$ خروجی ۱ را زمانی تولید می‌کند که یک رشته با طول  عضو آن زبان باشد و در غیر این صورت خروجی ۰ می‌دهد . خانواده‌ای از مدارها حداقل اندازه دارد اگر هیچ خانواده دیگری وجود نداشته باشد که بتواند با مدارهایی با اندازه کوچک‌تر نسبت به $C_n$ برای هر اندازه $n$ ورودی‌ها تصمیم‌گیری کند (و همین‌طور برای خانواده‌هایی که حداقل عمق دارند) . بنابراین، پیچیدگی مدار حتی برای زبان‌های غیر بازگشتی نیز معنادار است .مفهوم یک خانواده یکنواخت امکان ارتباط بین پیچیدگی مدار و معیارهای پیچیدگی مبتنی بر الگوریتم برای زبان‌های بازگشتی را فراهم می‌کند. اما، نوع غیر یکنواخت در یافتن کران‌های پایین برای میزان پیچیدگی مورد نیاز هر خانواده مدار برای تصمیم‌گیری درباره زبان‌های معین مفید است .تعریف رسمی پیچیدگی مدار یچیدگی اندازه مدار یک زبان رسمی $A$ به صورت تابعی $t:\mathbb{N}\to \mathbb{N}$ تعریف می‌شود که طول بیت ورودی $n$ را به پیچیدگی اندازه مدار حداقل $C_n$ نسبت می‌دهد . این مدار تصمیم می‌گیرد که آیا ورودی‌هایی با این طول عضو  هستند یا خیر. پیچیدگی عمق مدار نیز به طور مشابه تعریف می‌شود .

یکنواختی

مدارهای بولی یکی از نمونه‌های برجسته مدل‌های محاسباتی غیر یکنواخت هستند، به این معنی که ورودی‌های با طول‌های مختلف توسط مدارهای مختلف پردازش می‌شوند، برخلاف مدل‌های یکنواخت مانند ماشین‌های تورینگ که همان دستگاه محاسباتی برای تمام طول‌های ورودی ممکن استفاده می‌شود. یک مساله محاسباتی خاص با یک خانواده خاص از مدارهای بولی $C_1,C_2,\dots$ مرتبط است که در آن هر مدار $C_n$ ورودی‌هایی با n بیت را پردازش می‌کند . . معمولاً یک شرط یکنواختی بر روی این خانواده‌ها اعمال می‌شود که وجود یک ماشین تورینگ با محدودیت منابع را می‌طلبد که برای ورودی n توضیحی از مدار فردی $C_n$ را تولید کند . زمانی که زمان اجرای این ماشین تورینگ چندجمله‌ای در  باشد، خانواده مدارها به عنوان P _ یکنواخت شناخته می شود.شرط سخت‌گیرانه‌تر یکنواختی DLOGTIME _ یکنواخت کاربرد خاصی در مطالعه کلاس های کم عمق مدار همچون AC*0 یا TC*0 دارد . زمانی که هیچ محدودیت منابعی مشخص نشود، یک زبان بازگشتی است (یعنی قابل تصمیم‌گیری توسط یک ماشین تورینگ) اگر و تنها اگر زبان توسط یک خانواده یکنواخت از مدارهای بولی تصمیم‌گیری شود .

یکنواختی زمان چندجمله‌ای

یک خانواده مدارهای بولی $\{C_n:n\in \mathbb{N}\}$ یکنواخت زمان چندجمله‌ای است اگر یک ماشین تورینگ قطعی M وجود داشته باشد به طوری که

• M در زمان چندجمله‌ای اجرا می‌شود

• برای همه $n\in \mathbb{N}$ ، توضیح مدار $C_n$ را بر روی ورودی $1^n$ تولید می‌کند .

یکنواختی فضای لگاریتمی

یک خانواده مدارهای بولی $\{C_n:n\in \mathbb{N}\}$ یکنواخت فضای لگاریتمی است اگر یک ماشین تورینگ قطعی M وجود داشته باشد به طوری که

• M در فضای کاری لگاریتمی اجرا می‌شود (یعنی  یک ترانسدیوسر فضای لگاریتمی است)
• برای همه $n\in \mathbb{N}$ ، M توضیح مدار $C_n$ را بر روی ورودی $1^n$ تولید می‌کند.

تاریخچه

پیچیدگی مدار به سال 1949 برمی‌گردد، زمانی که شانون ثابت کرد که تقریباً تمام توابع بولی بر روی n متغیر به مدارهایی با اندازه Θ(2ⁿ/n) نیاز دارند . با وجود این حقیقت، نظریه‌پردازان پیچیدگی تاکنون نتوانسته‌اند یک کران پایین فوق‌خطی برای هیچ تابع مشخص اثبات کنند .

کران‌های پایین فوق‌چندجمله‌ای تحت شرایط خاصی برای خانواده مدارهای استفاده‌شده اثبات شده است .اولین تابعی که برای آن کران پایین فوق‌چندجمله‌ای مدارها نشان داده شد، تابع زوجیت است که مجموع بیت‌های ورودی خود را بر حسب مدول ۲ محاسبه می‌کند.. این واقعیت که تابع زوجیت در AC⁰ وجود ندارد، اولین‌بار به طور مستقل توسط آجتای در 1983 و توسط فرست، ساکس و سیپسر در 1984 اثبات شد . بهبودهای بعدی توسط هاستاد در 1987 نشان داد که هر خانواده‌ای از مدارهای با عمق ثابت که تابع زوجیت را محاسبه می‌کنند، به اندازه نمایی نیاز دارند. با گسترش نتیجه‌ای از رازبوروف، اسمولنسکی در 1987 اثبات کرد که این امر حتی در صورتی که مدار با گیت‌هایی که مجموع بیت‌های ورودی را بر حسب مدول یک عدد اول فرد p محاسبه می‌کنند، گسترش یابد، نیز درست است .

مساله k-clique این است که مشخص کنیم آیا یک گراف داده شده با n راس ، کلیکی به اندازه k دارد یا نه . برای هر انتخاب خاص از ثابت های n و k گراف می تواند به صورت دودویی کدگذاری شود با استفاده از $(\genfrac{}{}{0ex}{}{n}{2})$ و $f_k:\{0,1{\}}^{(\genfrac{}{}{0ex}{}{n}{2})}\to \{0,1\}$ این خانواده از توابع ، تک تن است و می توان آن را توسط خانواده ای از مدار ها محاسبه کرد ، اما نشان داده شده است که نمی توان ان را با خانواده ای از مدار های تک تن با اندازه چند جمله ای محاسبه کرد . نتیجه اصلی رازباروف در سال 1987 توسط آلن و بوپانو به یک کران پایین نمایی بهبود یافت . در سال 2008 راسمن نشان داد که مدار های عمق ثابت با دروازه های OR ، AND ، NOT برای حل مساله حتی در حالت متوسط $\mathrm{\Omega }(n^{k/4})$ استفاده شده . در حالت کلی مداری با اندازه $n^{k/4+O(1)}$ نیاز است .