درآمدی بر نظریه پیچیدگی

■ مقدمه

در این قسمت، پیوند میان منطق، الگوریتم‌ها و نظریه «پیچیدگی رایانشی» بررسی می‌کنیم. مفاهیم در اینجا به‌صورت ساده و شهودی معرفی شده‌اند و از پرداختن به جزئیات فنی ریاضی و منطقی پرهیز شده است. چرا که هدف، فراهم‌کردن یک تصویر کلی و قابل‌فهم از موضوع است. در بخش‌های بعدی، به همین مفاهیم با دقت و ژرفای بیشتری بازخواهیم گشت.

این قسمت از یک‌سو نشان می‌دهد که چگونه روش‌های سمانتیکی در منطق — مانند جدول ارزش — امکان تصمیم‌پذیری ماشینی درباره اعتبار استنتاج‌ها را فراهم می‌کنند، و از سوی دیگر روشن می‌شود که «تصمیم‌پذیر بودن» یک مسئله لزوماً به معنای «کارساز بودن» آن از نظر رایانشی نیست. این تمایز ما را به مفاهیمی بنیادین چون «پیچیدگی زمانی»، رشد چندجمله‌ای و نمایی، و تفاوت میان «حل یک مسئله» و «راست‌آزمایی» (Verification) پاسخ آن رهنمون می‌سازد.

⦁ پیچیدگی رایانشی و پیچیدگی سیستمیک

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

در مقابل، نظریه‌های عام پیچیدگی و سیستم‌های پیچیده بیشتر به رفتارهای برهم‌نهشتی (Superposition)، خودسازمان‌دهی و الگوهای کلان در سامانه‌های طبیعی یا اجتماعی می‌پردازند و الزاماً با رایانش‌پذیری سروکار ندارند. تاکید این بخش بر معنای پیچیدگی در منطق و علوم کامپیوتر است.

هدف ما در این قسمت، ارائه تصویری تدریجی و شهودی از نظریه پیچیدگی رایانشی، معرفی و طبقه‌بندی مسئله‌های (NP ،NP ،P-کامل و NP-سخت) است. تصویری که با مثال‌هایی ملموس از منطق، ریاضیات و علوم کامپیوتر همراه می‌شود.

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

■ ورودی و اندازه ورودی

در متن پیش رو، مراد از ورودی یک مجموعه متناهی است و اندازه ورودی (یا اندازه مسئله) اشاره به عدد اصلی آن مجموعه دارد. برای مثال، در حل مسئله تجزیه یک عدد به عوامل اول، ورودی رشته‌ متناهی رقم‌های آن عدد است و اندازه ورودی طول این رشته‌ است. یا در یک الگوریتم که مجموعه‌ای متناهی از اعداد صحیح، به فرض {۷, ۱۵, ۶, ۹}، را به صورت افزایشی مرتب می‌کند، ورودی، خود مجموعه و اندازه ورودی، کاردینال آن است و نیز مانند آنها.↧

■ تحلیل الگوریتم‌

تحلیل الگوریتم‌ کوشش برای تعیین پیچیدگی رایانشی آنها، یعنی پیش‌بینی میزان زمان و فضای (حافظه) مورد نیاز یک الگوریتم برای اجرا، با توجه به اندازه ورودی و نابسته به جزئیات پیاده‌سازی آنها است.

این تحلیل معمولاً با ماشین‌های انتزاعی و نمادگذاری‌هایی، که در ادامه خواهیم دید، انجام می‌شود. این کار معمولاً کار ساده‌ای نیست. چراکه رفتار واقعی الگوریتم می‌تواند قویاً به ساختار ورودی، حالت‌های حدی، انتخاب‌های درونی (مانند انتخاب «محور» در مرتب‌سازی به شیوه «مرتب‌سازی سریع» که در ادامه خوهیم دید)، و حتی مدل محاسباتی انتخابی وابسته باشد. به همین دلیل، یافتن کران‌های دقیق یا «مرتبه رشد واقعی» اغلب نیازمند استدلال‌های ظریف، ساده‌سازی‌های آگاهانه، و گاه پذیرش تحلیل‌های تقریبی یا میانگین‌حالت‌ها است.

■ یادآوری: کارآمدی استنتاج سمانتیکی (۱)

روند تعبیر در منطق گزاره‌ها یک روند کارآمد است. به این معنی که روش جدول ارزش، روندی را در اختیار می‌گذارد که به‌وسیله اجرای آن، ماشین می‌تواند درباره اعتبار یک استنتاج سمانتیکی دلخواه تصمیم‌گیری و پاسخ آری یا نه را در زمان محدود ارائه کند. اما این روند گرچه کارآمد است (در زمان محدود به پایان می‌رسد) ولی کارآمدی آن کارآمدی چندجمله‌ای (Polynomial Efficiency) نیست — یعنی، رشد زمان اجرای ماشینی این روند نسبت به رشد اندازه ورودی (تعداد متغیرهای گزاره‌ای متمایز در استنتاج معنایی) نمایی و نه چندجمله‌ای [فصل.۹، قسمت.۷ کتاب‌^{درآمد به منطق} (رشد جدول ارزش) را ببینید].

■ پیچیدگی زمانی

رشد زمان اجرای ماشینی یک الگوریتم نسبت به رشد اندازه ورودی‌، پیچیدگی زمانی (Time complexity) می‌نامیم.

بنابراین:

۱- پیچیدگی زمانی چندجمله‌ای برای حل یک مسئله (توسط یک الگوریتم قطعی) یعنی: تعداد گام‌های مورد نیاز برای حل آن مسئله توسط یک تابع چندجمله‌ای (برای مثال `n, n^2, n^3, n^60` که در آنها `n` اندازه ورودی است) محدود شده باشد.

۲- پیچیدگی زمانی نمایی برای حل یک مسئله (توسط یک الگوریتم قطعی) یعنی: تعداد گام‌های مورد نیاز برای حل آن مسئله توسط یک تابع نمایی (برای مثال `2^n ،3^n` یا به‌طور کلی `c^n` که در آن `n` اندازهٔ ورودی و `c>1` عددی ثابت است) محدود شده باشد.

مسئله‌ای با پیچیدگی زمانی نمایی در عمل و در اجرای ماشینی توسط کامپیوترهای رایج (کلاسیک) معمولاً مفید و کارساز نیستند. به چنین مسئله‌هایی در علوم کامپیوتر، بطور کلی، مسئله‌های سخت (Hard Problems) گفته می‌شود. زیرا با افزایش اندازه ورودی، زمان لازم برای حل این مسئله‌ها — حتی با سریع‌ترین ماشین‌های کلاسیک موجود یا قابل تصور — به‌سرعت چنان افزایش می‌یابد که حل آن‌ها در زمان درخور عملاً ناممکن می‌شود.

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

تفاوت بین رشد چند جمله‌ای و رشد نمایی در مثال زیر بیشتر آشکار می‌شود.

فرض کنید الگوریتم P و E را داریم، به قسمی که:

اجرای الگوریتم P حداکثر بعد از اجرای `n^۶` کاردستور پایان می‌یابد.

اجرای الگوریتم E حداکثر بعد از اجرای `۲^n` کاردستور پایان می‌یابد.

در ابتدا، `n^۶` حتی می‌تواند بزرگتر از `۲^n` باشد، بنابراین تابع نمایی هنوز ترسناک به نظر نمی‌رسد. اما پس از مدتی، `۲^n` به شدت افزایش می‌یابد. جدول زیر رشد اعداد را در کنار هم نشان می‌دهد.

`n`	`n^6`	`2^n`
۵	۱۵,۶۲۵	۳۲
۱۰	۱,۰۰۰,۰۰۰	۱,۰۲۴
۲۰	۶۴,۰۰۰,۰۰۰	≈ ۱,۰۰۰,۰۰۰
۳۰	۷۲۹,۰۰۰,۰۰۰	≈ ۱,۰۰۰,۰۰۰,۰۰۰
۴۰	۴,۰۹۶,۰۰۰,۰۰۰	≈ ۱,۰۰۰,۰۰۰,۰۰۰,۰۰۰
۵۰	۱۵,۶۲۵,۰۰۰,۰۰۰	≈ ۱,۰۰۰,۰۰۰,۰۰۰,۰۰۰,۰۰۰
۱۰۰	۱۰۱۲	≈ ۱۰۳۰
۲۰۰	۶.۴ × ۱۰۱۳	≈ ۱۰۶۰

می‌توان دید که تا حدود `n=20`، مقدار `n^6` حتی از `2^n` هم بزرگ‌تر است. حدود `n~~30`، این دو به‌هم نزدیک می‌شوند و از آن به بعد `2^n` با ‌سرعت نجومی بزرگ‌تر می‌شود. در `n=100`، اختلاف بسیار زیاد است: `n^6=10 ^ 12` و حال آنکه `2^n ~~ 10 ^ 30`. این مانند مقایسه یک تریلیون `(10 ^ 12)` با نونیلیون `(10^30)` است.

---

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

■ مثال. مسئله جستجو: جستجوی خطی

کیسه‌ای حاوی `n` مهره را در نظر بگیرید که هر کدام با شماره‌ای برچسب‌گذاری شده‌اند. شماره دلخواه `x` داده شده است و این پرسش که: آیا مهره‌ای با شماره `x` در کیسه وجود دارد؟

یک الگوریتم قطعی برای حل با جستجوی پی‌درپی به شرح زیر است:

۱. تا زمانی که هنوز در کیسه مهره است چرخه تکرار زیر را اجرا کن:

۱.۱ → ۱.۲ → ۱.۳ → ۱.۱ → ...	۱.۱	یک مهره از کیسه بدون بازگذاری آن از کیسه بیرون کشید شود.
	۱.۲	اگر برچسب مهره بیرون کشیده شده با `x` داده شده برابر است، الگوریتم با پاسخ "بله" پایان یاید.
	۱.۳	اگر برچسب مهره بیرون کشیده شده با `x` داده شده برابر نیست، آن مهره کنار گذاشته شود.

۲. الگوریتم با پاسخ "نه" پایان یاید.

صحت این الگوریتم تضمین شده است، زیرا در صورت لزوم همه مهره‌ها را بررسی می‌کند. پیچیدگی زمانی در بدترین حالت برابر تکرار `n` بار گام‌های ۱.۱ تا ۱.۳ است که وقتی رخ می‌دهد که مهره هدف آخرین مهره کشیده شده باشد یا اصلاً چنین مهره‌ای در کیسه نباشد. این نمونه‌ای از یک روش جستجوی خطی و سرراست است که در آن تعداد مراحل مورد نیاز مستقیماً با اندازه ورودی `(n)` متناسب است. بنابراین درجه پیچیدگی زمانی چندجمله‌ای (درجه یک) است.

■ مثال. مسئله مرتب‌سازی: (مرتب سازی حبابی)

فرض کنید `n` مهره داریم که هر کدام با یک شماره منحصر به فرد برچسب‌گذاری شده‌اند و در یک ردیف روبروی ما قرار گرفته‌اند. هدف این است که آنها را از چپ به راست به ترتیب عددی افزایشی مرتب کنیم.

• الگوریتم مرتب سازی حبابی:

یک روش برای حل این مسئله، الگوریتم مرتب‌سازی حبابی (Bubble Sort Agorithm) است. این الگوریتم از طریق مقایسه‌های دوتایی و جابه‌جایی عناصر مجاور عمل می‌کند. به‌گونه‌ای که عناصر بزرگ‌تر، مانند حباب‌هایی که به سطح آب می‌آیند، به‌تدریج به سمت انتهای فهرست حرکت می‌کنند.

۱. آغاز: با دو مهره سمت چپ در ردیف شروع می‌کنیم.

۲. مقایسه و جابجایی: دو مهره مجاور را با یکدیگر مقایسه می‌کنیم.

اگر شماره مهره سمت چپ بزرگتر از شماره مهره سمت راست است، آنها را جابجا می‌کنیم.

اگر مهره‌ها از پیش به ترتیب افزایشی باشند (راست ≥ چپ)، جابجایی انجام نمی‌شود و به گام بعد می‌رویم.

۳. حرکت به راست: توجه را به یک مهره به سمت راست می‌بریم. اکنون یک جفت جدیدی برای بررسی داریم (مهره‌ تازه "حباب" شده و مهره بعدی). مرحله ۲ را تکرار می‌کنیم.

۴. تکمیل یک چرخه: این روند مقایسه و جابجایی جفت‌های مجاور را تا رسیدن به انتهای ردیف ادامه می‌دهیم. در پایان این چرخه، بزرگ‌ترین مهره در میان عناصر نامرتب، در راست‌ترین موقعیت قرار می‌گیرد.

۵. تکرار و باریک کردن دامنه مقایسه: به ابتدای ردیف بازمی‌گردیم و چرخه جدیدی را آغاز می‌کنیم؛ اما این بار می‌توان آخرین مهره چرخه قبلی را نادیده گرفت، زیرا آن مهره اکنون در جای نهایی و مرتب‌شده خود قرار دارد.

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

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

برای نمونه الگوریتم را برای مرتب‌سازی رشته [۴، ۲، ۳، ۱]  اجرا می‌کنیم:

چرخه ۱:

(۴ ↔ ۲) ↣ [۲، ۴، ۳، ۱]

(۴ ↔ ۳) ↣ [۲، ۳، ۴، ۱]

(۴ ↔ ۱) ↣ [۲, ۳, ۱, ۴]

اکنون ۴ در جای خود است.

چرخه ۲:

(۲, ۳) مرتب است ↢:

(۳ ↔ ۱) ↣ [۲, ۱, ۳, ۴]

اکنون ۳ در جای خود است.

چرخه ۳:

(۲ ↔ ۱) ↣ [۱, ۲, ۳, ۴]

اکنون ۲ در جای خود است. مهره باقی مانده (۱) بطور ضمنی مرتب شده است.

پایان چرخه‌ها: رشته ورودی اکنون مرتب شده است: [۱, ۲, ۳, ۴].

پیچیدگی زمانی:

در بدترین حالت (وقتی رشته ورودی به ترتیب وارون، یعنی بزرگ به کوچک، باشد)، به `n-۱` بار چرخه نیاز است. اولین چرخه `n-۱` مقایسه، چرخه بعدی `n-۲` و به همین ترتیب ادامه می‌یابد. این مجموع تقریباً `n^۲/۲` مقایسه و جابجایی است که پیچیدگی زمانی بدترین حالت آن چندجمله‌ای درجه دوم (`n^۲`) است.

برخلاف مسئله جستجو که به یک پرسش بله/نه پاسخ می‌دهد، مرتب‌سازی یک کار بازآرایی عناصر است. مرتب‌سازی حبابی یک مثال مقدماتی برجسته است که نشان می‌دهد چگونه تکرار یک چرخه ساده از عملیات می‌تواند در نهایت منجر به نظم شود. منطق آن به راحتی قابل درک است، اما از آنجا که عملکرد آن با رشته‌های بزرگ داده‌ها به سرعت کاهش می‌یابد (پیچیدگی درجه دوم)، الگوریتم‌های پیچیده‌تری که مسئله را به طور کارآمد به زیرمسئله‌ها (تجزیه و ترکیب) کاهش [با درجه پیچیدگی: `nLn(n)`] می‌دهند، برای کارهای دنیای واقعی ترجیح داده می‌شوند.

■ مثال. مسئله جستجو: جستجوی دودویی (Binary search)

در مسئله جستجی خطی، ورودی‌ها گردایه‌ای از عناصر و عنصری برای یافتن آن در آن گردایه‌ بود.

در مسئله جستجوی دودویی، که در ادامه شرح داده خواهد شد، فرض بر این است که ورودی یک دنباله متناهی از عناصر است که بر اساس یک رابطه ترتیبی معین (برای مثال ترتیب عددی یا واژگانی) مرتب شده‌اند. عناصر این دنباله می‌توانند اعداد، رشته‌ها‌ (نام‌ها)، یا به‌طور کلی عناصری از هر گونه‌ای باشند که مقایسه‌پذیر باشند.

با توجه به مرتب بودن دنباله ورودی در جستجوی دودویی، می‌توان از این ساختار برای کاهش فضای جستجو بهره برد. در هر چرخه از الگوریتم، عنصر میانی دنباله با عنصر مورد نظر مقایسه می‌شود. اگر این دو برابر نباشند، با توجه به ترتیب عناصر، می‌توان با قطعیت یکی از دو نیمه دنباله را به‌طور کامل کنار گذاشت و چرخه جستجو را فقط در نیمه دیگر ادامه داد. بدین ترتیب، در هر مرحله اندازه مسئله تقریباً به نصف کاهش می‌یابد. این ویژگی مستقیماً مبنای تحلیل پیچیدگی زمانی جستجوی دودویی را تشکیل می‌دهد.

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

■ الگوریتم جستجوی دودویی

ورودی: آرایه‌ای مرتب‌شده از عناصر دنباله `U_n = < u_۱, ..., u_n>`

عنصر مورد نظر برای جستجو: `x`

خروجی: اندیس عنصر `x` در دنباله (در صورت وجود)، یا پاسخ منفی

۱. `Left leftarrow u_۱;` `Right leftarrow u_n ;`

۲. تا زمانی که `Left <= Right` برقرار است چرخه تکرار زیر را اجرا کن:

۲.۱	`mid leftarrow |__ (Left + Right)/۲ __|`
۲.۲	اگر `U[mid] = x`  آنگاه: الگوریتم با پاسخ `mid` به‌عنوان اندیس یافته پایان یاید.
۲.۳	اگر `U[mid] > x` آنگاه: `Right leftarrow mid -۱`
۲.۴	اگر `U[mid] < x` آنگاه: `Left leftarrow mid +۱`

۳. الگوریتم با پاسخ "نه" پایان یاید.

فرض کنید اندازه ورودی ۱۰۲۴ باشد (یعنی، جستجو در میان ۱۰۲۴ عنصر باید انجام شود). در زیر حداکثر تعداد چرخش چرخه تکرار جستجو آمده است.

#۱: ۱۰۲۴ `larr` ۵۱۲ عنصر باقی می‌ماند
#۲: ۵۱۲ `larr` ۲۵۶
#۳: ۲۵۶ `larr` ۱۲۸
#۴: ۱۲۸ `larr` ۶۴
#۵: ۶۴ `larr` ۳۲
#۶: ۳۲ `larr` ۱۶
#۷: ۱۶ `larr` ۸
#۸: ۸ `larr` ۴
#۹: ۴ `larr` ۲
#۱۰: ۲ `larr` ۱

نکته مهم:

هر بار که اندازه مسئه دو برابر شود، فقط یک دور به تعداد چرخه‌های جستجو اضافه می‌شود.

پیچیدگی زمانی جستجوی دودویی لگاریتمی است

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

فرض می‌کنیم:

• `n` اندازه اولیه دنباله باشد،

• در هر چرخش اندازه دنباله نصف می‌شود،

• بعد از `k` چرخش فقط یک عنصر باقی بماند:

پس خواهیم داشت:

`۱ = ` `ubrace(۱/۲ xx ... xx ۱/۲)_("k")‍ =` ` n / ۲^k`‍‍‍‍`=>`  `n =۲^k``=>` `log (n) =k`

یعنی: تعداد دور‌های لازم برای جستجوی دودویی متناسب با لگاریتم اندازه ورودی است. به عبارت دیگر، پیچیدگی زمانی جستجوی دودویی لگاریتمی، `log (n)`، است.

---

■ مثال. مسئله مرتب سازی: مرتب سازی سریع

کوئیک‌سورت یک الگوریتم «تقسیم‌ و‌ حل (Divide & Conquer)» است. یعنی، مرتب‌سازی با تکیه بر تقسیم تدریجی آرایه انجام می‌شود. ابتدا یک عنصر از آرایه به‌عنوان عنصر محور انتخاب می‌شود. سپس آرایه به‌گونه‌ای بازآرایی می‌گردد که تمام عناصری که مقدارشان از عنصر محوری کوچک‌تر است در سمت چپ آن قرار گیرند و تمام عناصری که مقدارشان بزرگ‌تر است در سمت راست آن واقع شوند. پس از این مرحله، عنصر محور در جای نهایی خود قرار می‌گیرد.

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

فرض کنید انتخاب محور «مناسب» باشد، یعنی آرایه را به دو بخش با اندازه‌های تقریباً برابر تقسیم کند. بنابراین:

• در دور یکم:
  کل آرایه با `n` عنصر یک‌بار پیمایش می‌شود.
• در دور دوم:
  دو آرایهٔ با اندازهٔ تقریباً `n/۲` مرتب می‌شوند.
• در مرحله سوم:
  چهتر آرایه با اندازهٔ تقریباً `n/۴` مرتب می‌شوند.
• ...

در هر «سطح» از این فرایند:

• مجموع تعداد عناصری که بررسی می‌شوند ≈ `n`

• و تعداد سطح‌ها ≈ `log (n)`

مثال عددی:

اگر `۲^(۱۰)`= ۱۰۲۴ = `n`:

• سطح اول: ۱۰۲۵ مقایسه،
• سطح دوم: ۲ × ۵۱۲ = ۱۰۲۴،
• سطح سوم: ۴ × ۲۵۶ = ۱۲۰۴
• ....،

پس کل کار انجام‌شده:

 ۱۰۲۴ ‍× ۱۰ = ۱۰۲۴ × `log` (۱۰۲۴)

 

 

■ مقدمه به نظریه پیچیدگی رایانشی (Computational complexity theory)

در این بند، کوتاه برخی مفاهیم نظریه پیچیدگی رایانشی (محاسباتی) را معرفی می‌کنیم.

پیش از آن‌که به مقدمات مباحث نظریه پیچیدگی رایانشی بپردازیم، لازم است بحث تصمیم‌پذیری را که پیش‌تر در قسمت «روندِ منطق» طرح شد، یک گام گسترش دهیم و کلیدواژه راست‌آزمایی (Verification) را بیشتر بشکافیم. در آن‌جا دیدیم که یک مسئله منطقی وقتی تصمیم‌پذیر است که روشی صوری (الگوریتم) در اختیار داشته باشیم که برای هر ورودی ممکن، در زمان محدود، پاسخ «آری» یا «نه» بدهد. اکنون می‌خواهیم تمایز میان «توانایی حل ماشینی» و «توانایی راست‌آزمایی ماشینی یک پاسخ پیشنهادی» را آشکارتر کنیم: گاهی ماشین نمی‌تواند در زمان درخور، از ابتدا به پاسخ برسد، اما اگر پاسخی به او داده شود، می‌تواند در زمانی کوتاه درستی یا نادرستی آن را بررسی کند.

برای روشن‌تر شدن این تفاوت بنیادی میان «حل کردن» و «راست‌آزمایی»، به سراغ چند نمونه عینی می‌رویم. در هر یک از این مثال‌ها خواهیم دید که چگونه ممکن است یافتن یک پاسخ، از نظر رایانشی بسیار دشوار باشد، در حالی‌که اگر همان پاسخ به‌عنوان «حدس» در اختیار ماشین قرار گیرد، راست‌آزمایی درستی یا نادرستی آن در زمانی به‌مراتب کوتاه‌تر انجام می‌گیرد.

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

■ راست‌آزمایی (Verification)

راست‌آزمایی (Verification) پاسخ داده ‌شده برای موردی از یک مسئله نوعی متفاوت از حل آن مسئله نوعی است. در زیر کوشش شده است با آوردن چهار مثال کاربردی تفاوت این دو توضیح داده شود.

این تفاوت از آن‌رو مهم است که در بسیاری از مسئله‌ها، راست‌آزمایی یک پاسخ پیشنهادی، بسیار ساده‌تر از خود پیدا کردن آن جواب از از آغاز است. در عمل، در حل بسیاری از مسائل دشوار، ما معمولاً نمی‌دانیم چگونه مستقیماً «بهترین» پاسخ را با روشی سریع پیدا کنیم، اما اگر کسی یک پاسخ پیشنهادی یا یک «گواه» ارائه کند، ممکن است بتوانیم با چند محاسبه نسبتاً ساده بررسی کنیم که آیا این پاسخ واقعاً مسئله را حل می‌کند یا نه. مثال‌هایی که در ادامه می‌آیند دقیقاً برای برجسته‌کردن همین نکته‌اند: این‌که در چه مسائلی «راست‌آزمایی یک پاسج داده‌شده» کار نسبتاً آسانی است، در حالی‌که «خود یافتن آن جواب» می‌تواند به‌طرز شدیدی وقت‌گیر و از نظر رایانشی‌ سخت‌ باشد. فهم این تفاوت، پایه‌ای است برای مفاهیمی که در ادامه درباره آن‌ها صحبت خواهیم کرد.

مثال ۱. مسئله معادله درجه دو

راست آزمایی پاسخ موردی از معادله درجه دو، به فرض ۳، برای معادله:

`x^۲+۶=۵x`

۳^۲ + ۶ = ۵ `xx` ۳

یک مسئله و یافتن راه حل کلی معادله `a x^۲ +bx + c=۰` به صورت جبری مسئله دیگر است.

حل یک معادله درجه دوم با ضرایب حقیقی، به بیش از چند محاسبه ساده نیاز ندارد و درواقع درجه پیچیدگی آن چندجمله‌ای (در این‌جا تابع ثابت) است. اکنون فرض کنید Q یک معادله درجه دوم با ضرایب حقیقی باشد. مسئله تصمیم‌پذیری «آیا Q دارای ریشه حقیقی است؟» چه در حالت پاسخ «آری» و چه در حالت پاسخ «نه»، در زمان چندجمله‌ای قابل راست‌آزمایی است، چراکه در هر دو حالت کافی است الگوریتم حل معادله درجه دوم را اجرا کنیم [مثلاً با محاسبه دلتای آن، یعنی `b^۲ - ۴ac`]. این وضعیت برای همه مسئله‌های تصمیم‌پذیری که درجه پیچیدگی خود آن‌ها چندجمله‌ای است برقرار است:

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

در ادامه، مثال‌هایی را می‌بینیم که در آن‌ها درجه سختی راست‌آزمایی پاسخ «آری» و پاسخ «نه» یکسان نیست.

■ مسئله استنتاج سمانتیکی (۲)

راست‌آزمایی یک صورت توتولوژیک برای یک گمارش معین مقادیر ارزش، مسئله‌ای با  کارآمدی چندجمله‌ای است ولی اثبات صورت توتولوژیک بودن آن توسط جدول ارزش یک مسئله سخت (با درجه پیچیدگی نمایی) است [فصل.[۹، قسمت.۷ کتاب‌^{درآمد به منطق} — رشد جدول ارزش]. برای مثال اگر یک الگوریتم بر پایه جدول ارزش برای توتولوژیک بودن یک فرمول خوش-ساخت منطق گزاره‌ای پاسخ «نه» بگوید، این الگوریتم بالقوه می‌تواند یک گمارش مقادیر ارزش نقض را نیز ارائه دهد. اکنون به آسانی می‌توان این پاسخ را راست‌آزمایی کرد. امّا اگر پاسخ الگوریتم «آری» باشد، برای اثبات توتولوژیک ‌بودن فرمول به روش جدول ارزش، ناگزیر باید همه گمارش‌های ممکن مقادیر ارزش به متغیرها را بررسی کنیم، کاری که زمان لازم برای آن، نسبت به تعداد متغیرها رشد نمایی دارد.

■ مسئله چرخه همیلتونی (Hamiltonian cycle problem)

شکل زیر، دو نمودار (گراف) ۱ و ۲ را نشان می‌دهد که گره‌ها و یال‌های آنها (برای مثال) شهرها و مسیرهای بین آنها هستند.

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

به چرخه‌هایی که در آن‌ها از هر گره دقیقاً یک بار (و نهایتاً بازگشت به گرهٔ آغازین) گذر می‌شود، چرخه همیلتونی (Hamiltonian cycle) می‌گویند.

نشان‌دادن این‌که یک گراف داده‌شده دارای چرخه همیلتونی است، یک مسئله سخت از دیدگاه رایانشی است (پیچیدگی زمانی آن، در بدترین حالت، نمایی در تعداد گره‌هاست. تصور کنید این گراف، نقشه راه‌های یک کشور با صدها شهر و مسیر باشد). اما اگر کسی یک چرخه همیلتونی را به‌عنوان پاسخ «آری» به ما نشان دهد مثلاً دنباله‌ای از شهرها که از هر شهر یک بار گذشته و به شهر آغازین برمی‌گردد راست‌آزمایی این پاسخ ساده و زمانی چندجمله‌ای است: کافی است وارسی کنیم که:

۱. هر شهر دقیقاً یک بار در فهرست آمده باشد،

۲. هر دو شهر متوالی در این فهرست با یک یال در گراف به‌هم پیوند شده باشند،

۳. شهر پایانی به شهر آغازین پیوند شده باشند.

همه این وارسی‌ها را می‌توان در زمانی متناسب با تعداد گره‌ها و یال‌های گراف انجام داد.

اما چه در باره پاسخ «نه»؟

اگر الگوریتمی ادعا کند که «این گراف هیچ چرخه همیلتونی ندارد»، در حالت عادی گواه ساده و کوتاهی که در زمان چندجمله‌ای بتوان آن را راست‌آزمایی کرد، در دسترس نیست. به عبارت دیگر، برای نفی وجود یک چرخه همیلتونی، معمولاً لازم است (حداقل در بدترین حالت) به‌نوعی تمامی حالت‌های ممکن یا ساختارهای پیچیده‌ای را بررسی کنیم که از نظر زمانی هزینه‌بر و نمایی است. برای پاسخ «آری»، یک گواه (خود چرخه) وجود دارد که در زمان قابل راست‌آزمایی است، اما برای پاسخ «نه» گواه چندجمله‌ای شناخته‌شده‌ای نداریم.

■ مسئله فروشنده دوره‌گرد (Traveling Salesman Problem)

در شکل زیر یک گراف وزن‌دار بازنمایی شده است که در آن گره‌ها شهرها و یال‌ها جاده‌های بین آن‌ها هستند و روی هر یال عددی نوشته شده که میانگین هزینه سفر (وزن یال واسط) بین راهی دو شهر را نشان می‌دهد.

در این گراف، یک فروشنده دوره‌گرد می‌خواهد سفر خود را از یک شهر آغاز کند، از هر شهر دقیقاً یک بار عبور کند و در پایان به شهر آغازین بازگردد، به‌قسمی‌که جمع کل هزینه بین راهی مسیر از یک مقدار معین (برای مثال مقدار `v`) بیشتر نشود. پرسش این است که:

آیا در این گراف، مسیری چرخه‌ای وجود دارد که از هر شهر دقیقاً یک بار بگذرد و هزینه کل بین راهی آن حداکثر `v` باشد؟

پاسخ (برای مثال: A-B-C-D-A) را به شیوه زیر راست‌آزمایی می‌کنیم:

1. هر شهر، بجز شهر آغازین، دقیقاً یک بار در فهرست ظاهر شده است،
2. بین هر دو شهر متوالی در این فهرست، جاده‌ای در گراف وجود دارد،
3. جمع هزینه تمام یال‌های این مسیر حداکثر `v` است.

همهٔ این محاسبه‌ها را می‌توان در زمانی چندجمله‌ای نسبت به تعداد شهرها و یال‌ها انجام داد .

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

■ مسئله بهینه‌سازی فروشنده دوره‌گرد (TSP-OPT / Traveling Salesman Problem Optimization)

گراف وزن‌دار زیر (شکل زیر) را در نظر بگیرید که در آن وزن هر یال عددی نامنفی است و آن را هزینه طی‌کردی آن یال می‌نامیم (برای سادگی می‌توانید آن را مسافت جاده نیز در نظر بگیرید).

در نسخه بهینه‌سازی مسئله فروشنده دوره‌گرد، پرسش دیگر فقط این نیست که: «آیا سفری وجود دارد که از هر شهر دقیقاً یک بار بگذرد و مجموع مسافت پیموده آن حداکثر `v` باشد؟» بلکه پرسش این است که:

«کم‌هزینه‌ترین سفر که از هر شهر دقیقاً یک‌بار می‌گذرد و به شهر آغازین بازمی‌گردد یعنی سفری که مجموع هزینهٔ یال‌های آن کمینه است چه هزینه‌ای دارد؟»

فرض کنید سفر مشخص T ارائه و نیز و ادعا شده است که:

«T کم‌هزینه‌ترین (کوتاه‌ترین) سفر ممکن است».

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

امّا برای راست‌آزمایی پاسخ «نه»، یعنی برای رد این ادعا که «T کم‌هزینه‌ترین سفر نیست»، کافی است یک مثال نقض ارائه شود. فرض کنید سفری دیگر T′ به‌عنوان گواه داده شده باشد. برای بررسی این گواه باید:

۱. وارسی کرد که T′ نیز یک گردش معتبر است (از هر شهر دقیقاً یک‌بار می‌گذرد و به شهر شروع بازمی‌گردد)،

۲. هزینه سفر T و هزینه سفر T′ را محاسبه و مقایسه کنیم که آیا هزینه(T`) < هزینه(T) یا نه.

این وارسی‌ها را می‌توان در زمانی چندجمله‌ای نسبت به اندازه گراف انجام داد. بنابراین برای پاسخ «نه» یک گواه کوتاه وجود دارد که راست‌آزمایی آن از نظر رایانشی آسان است.

■ طبقه‌بندی سختی مسئله (Problem hardness classification)

■ مسئله P

مسئله‌ کلاس P آن رده از مسئله‌های تصمیم‌پذیری هستند که الگوریتم قطعی با پیچیدگی زمانی چندجمله‌ای برای حل آنها وجود دارد. (مسئله جستجو، مسئله مرتب‌سازی، الگوریتم اقلیدس)

اگر `A` و `B` دو مسئله P باشند، آنگاه `A` به `B` کاهش‌پذیر است. به عبارت دیگر:

`‌"A" in "P" , ‌"B" in "P" => "‌A" <=_p "B"`

---

■ مسئله ‌ NP

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

NP = مسئله‌های تصمیم‌پذیری که پاسخ‌های «آری» آن‌ها اثبات‌های کوتاه و قابل راست‌آزمایی با پیچیدگی زمانی چندجمله‌ای است.

NP کوتاه‌شده Nondeterministic Polynomial time — زمان چندجمله‌ای غیرقطعی است. این رده مسئله‌ها از دیدگاه نظری با یک الگوریتم غیر-قطعی با پیچیدگی زمانی چندجمله‌ای قابل حل هستند.

اگر مسئله‌ای، به‌فرض `E`، در زمان چندجمله‌ای قابل حل باشد (یعنی `E in bb "P"`)، آنگاه می‌توان هر پاسخ پیشنهادی برای آن را نیز در زمان چندجمله‌ای راست آزمایی کرد؛ زیرا خود الگوریتم حل‌کننده می‌تواند به‌عنوان الگوریتم راست‌آزمایی به کار رود. بنابراین، `E` عضو NP نیز هست و در نتیجه می‌توان نوشت:

`bb "P " sube bb " NP"`

درواقع، رابطه بالا بدیهی است، زیرا «حل کردن» قوی‌تر از «راست‌آزمایی کردن» است.

اکنون این پرسش مطرح می‌شود: آیا مسئله‌ای وجود دارد که عضو NP باشد ولی در P نباشد؟ دیدیم که مسئله چرخه همیلتونی مسئله‌ای در NP است. آیا می‌توان الگوریتمی یافت که این مسئله را در زمان چندجمله‌ای حل کند؟ یا می‌توان برهانی ارائه داد که نشان دهد چنین الگوریتمی وجود ندارد؟ این پرسش هنوز پاسخی قطعی ندارد و یکی از مسائل باز بنیادی در علوم کامپیوتر نظری است. اگر نشان داده شود که مسئله‌ای در NP وجود دارد که در P قرار ندارد، آنگاه نتیجه خواهد شد که `bb "P " != bb " NP"`.

■ مسئله NP-کامل (NP-Complete)

درون کلاس NP، زیرکلاسی از مسئله‌ها وجود دارد که آنها را مسئله NP-کامل (NP-Complete) می‌نامند. این مسئله‌ها از دیدگاه نظری، «سخت‌ترین» مسئله‌های کلاس NP به‌شمار می‌آیند.

به‌طور دقیق، یک مسئله NP-کامل مسئله‌ای است که:

۱. عضو NP باشد و هم

۲. هر مسئله در NP بتواند در زمان چندجمله‌ای به آن کاهش‌ یابد.

از آنجا که هر مسئله NP-کامل عضو کلاس NP است، راست‌آزمایی پاسخ «آری» آن (در قالب یک مسئله تصمیم‌پذیری آری/نه) در زمان چندجمله‌ای میسر است.

مسئله فروشنده دوره‌گرد در قالب یک مسئله تصمیم‌پذیری یک مسئله NP-کامل است.

افزون بر آنچه گفته شد، اگر برای حتی یکی از این مسئله‌های NP-کامل الگوریتمی با زمان چندجمله‌ای یافت شود، آنگاه همه مسئله‌های NP در زمان چندجمله‌ای حل‌پذیر خواهند بود. در این صورت خواهیم داشت:

P = NP

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

باور عام دانشمندان علوم کامپیوتر و منطق‌دانان آن است که:
P`ne`NP

■ مسئله NP-سخت (NP-Hard)

یک مسئله ‌NP-سخت (NP-Hard) مسئله‌ای است که دست‌کم به اندازه سخت‌ترین مسئله‌های NP دشوار است. به‌طور دقیق، مسئله‌ای مسئله ‌NP-سخت نامیده می‌شود اگر هر مسئله در NP را بتوان در زمان چندجمله‌ای به آن کاهش داد.

نکته مهم این است که مسئله‌های NP-سخت لزومی ندارد عضو NP باشند. ممکن است حتی در زمان چندجمله‌ای نیز قابل راست‌آزمایی نباشند. نمونه‌هایی از این دست شامل نسخه‌های بهینه‌سازی برخی مسئله‌ها (مانند نسخه بهینه‌سازی مسئله فروشنده دوره‌گرد) یا حتی مسئله‌هایی مانند مسئله توقف هستند.

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

مقایسه NP-کامل و NP-سخت
NP-سخت	NP-کامل	ویژگی
✔	✔	همه مسئله‌های NP به آن کاهش‌پذیرند.
لزوماً نه	✔	عضو NP است.
لزوماً نه	✔	پاسخ «آری» در زمان چندجمله‌ای قابل راست‌آزمایی است.

■ کامپیوترهای کوانتمی و مسئله‌های سخت

در بخش‌های «صورت، معنی و مدل - منطق گزاره‌ها» (کامپیوترهای کوانتمی و پیچیدگی نمایی) و «جبر بول و مدارهای منطقی» (کیوبیت‌ها (Qubit) و گسترش بنیان‌های منطقی) مقدمه‌ای بر رایانش کوانتومی ارائه شد. اکنون ادامه آن را اندکی بیشتر کاوش می‌کنیم.

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

الگوریتم‌های کلاسیک به‌صورت گام‌به‌گام و بر اساس وضعیت‌های دوتایی (Binary) معین اجرا می‌شوند. در مقابل، الگوریتم‌های کوانتومی بر تحول حالت‌های کوانتومی استوارند که می‌توانند در برهم‌نهی خطی حالت‌های پایه قرار گیرند و از پدیده درهم‌تنیده‌گی و تداخل کوانتومی↖ برای تقویت مسیرهای منتهی به پاسخ درست بهره ببرند. واحد بنیادی رایانش کوانتومی، یعنی بیت کوانتومی (Qubit)، پیش از اندازه‌گیری دارای مقدار دوتایی مشخص (صفر یا یک) نیست، بلکه حالت آن به‌صورت ترکیبی از حالت‌های ممکن توصیف می‌شود. این ویژگی به معنای نقض منطق کلاسیک یا روند دوارزشی نیست، بلکه نشان می‌دهد که پیش از فرآیند اندازه‌گیری، نسبت‌دادن مقادیر صدق کلاسیکی به حالت فیزیکی سیستم موجه نیست. از این رو، در توصیف ساختار گزاره‌های مربوط به مشاهده‌های کوانتومی، گاه از چارچوبی موسوم به «منطق کوانتمی» استفاده می‌شود. چارچوبی که ناظر به ویژگی‌های تجربی سامانه‌های کوانتومی است و جایگزین منطق کلاسیک در استدلال ریاضی یا الگوریتمی به‌شمار نمی‌آید. در نتیجه، رایانش کوانتومی نه با کنارگذاشتن منطق کلاسیک، بلکه با تکیه بر قوانین فیزیکی متفاوت، امکان حل کارآمدتر برخی مسائل را — که برای کامپیوترهای کلاسیک سخت‌اند — فراهم می‌کند. به این معنا، محاسبات کوانتومی مرزهای عملی پیچیدگی رایانشی را جابه‌جا می‌کند و افق‌های تازه‌ای برای فهم رابطه میان محاسبه، صدق و برهان می‌گشاید.

یک فضای جواب با پیچیدگی نمایی را یک هزارتوی وسیع و تاریک تجسم کنید. یک کامپیوتر کلاسیک ممکن است نیاز داشته باشد که هر راهرو را تا یافتن راهروی خروج بپپماید. یک کامپیوتر کوانتومی، اگر هزارتو الگوی پنهان خاصی داشته باشد، می‌تواند از اثرات کوانتومی برای «حس کردن» راهروی خروج بسیار سریع‌تر استفاده کند. اما اگر این هزارتو واقعاً دلخواه و آشوبناک باشد و هیچ الگویی برای بهره‌برداری نداشته باشد، حتی یک کاوشگر کوانتومی نیز در کاوش بخش قابل توجهی از راهروها گیر خواهد کرد.

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

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

■ مسئله‌های سخت و هوش مصنوعی

کتاب «برنامه = ‌ الگوریتم ‌+ ساختارهای داده»:

در سال م۱۹۷۶ (ش۱۳۵۴) توسط نیکلاس ویرث نوشته شده و یکی از تاثیرگذارترین کتاب‌های علوم کامپیوتر در زمان خود است و مانند سایر آثار ویرث، به طور گسترده در آموزش مورد استفاده قرار گرفته است.

عنوان این کتاب، که آن را معادله ویرث می‌نامیم، بیانگر این ایده بنیادین است که الگوریتم‌ها به‌تنهایی برنامه نمی‌سازند و داده‌ها نیز بدون یک روند پردازشی معنا ندارند. آنچه برنامه واقعی را پدید می‌آورد، ترکیب منسجم الگوریتم با ساختار داده (برای مثال ساختار ماتریسی را در حل مسئله) مناسب است. الگوریتم مشخص می‌کند چه کاری باید انجام شود، اما ساختار داده تعیین می‌کند در چگونه فضایی داده‌ها اقامت و در دسترس قرار گیرند. انتخاب نادرست هر یک می‌تواند کل سامانه را ناکارآمد یا حتی غیرقابل استفاده کند.

از این دیدگاه، کارایی، سادگی و درستی یک برنامه نه صرفاً نتیجه انتخاب و طراحی الگوریتم، بلکه حاصل هماهنگی الگوریتم با ساختار دادهای مناسب است. بسیاری از مسئله‌ها با تغییر ساختار داده — و نه الگوریتم — به‌طور چشمگیری ساده‌تر یا سریع‌تر می‌شوند. بنابراین، این عنوان به‌صورت فشرده می‌گوید: برنامه‌نویسی کارساز طراحی هم‌زمان الگوریتم و ساختار داده‌ها است.

اگر از ایده ویرث (یعنی، برنامه = ‌ الگوریتم ‌+ ساختارهای داده‌) آغاز کنیم، یعنی، اینکه «برنامه حاصل ترکیب الگوریتم و ساختار داده است»، به‌طور منطقی خیلی زود به این پرسش می‌رسیم که: آیا برای هر مسئله‌ای، با انتخاب الگوریتم و ساختار داده مناسب، می‌توان به برنامه‌ای کارساز رسید؟ این دقیقاً همان نقطه‌ای است که بحث زمینه اصلی ما، یعنی «مسئله‌های سخت» وارد می‌شود. نظریه پیچیدگی رایانشی در اصل پاسخی نظام‌مند به همین تردید است: اینکه محدودیت‌ها فقط ناشی از ضعف طراحی نیستند، بلکه گاه سرشت خود مسئله هستند.

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

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

با این حال، هوش مصنوعی (AI) نکته‌ای تازه می‌افزاید: برنامه دیگر فقط حاصل طراحی صریح انسان نیست، بلکه نتیجه تعامل الگوریتم با داده‌های عظیم است. می‌توان گفت معادله ویرث امروز به‌شکلی گسترش‌یافته چنین خوانده می‌شود:

داده‌ها + ساختارهای داده‌ها + الگوریتم = رفتار

منظور از رفتار در معادله بالا، الگوی قابل مشاهده عملکرد یک سیستم محاسباتی در عمل است، نه آنچه «روی کاغذ» نوشته شده، بلکه آنچه واقعاً، وقتی سیستم با داده و محیط روبرو می‌شود رخ می‌دهد، است. به‌طور دقیق‌تر، منظور از رفتار  عبارت است از:

• خروجی‌هایی که سیستم تولید می‌کند،
• شیوه واکنش آن به ورودی‌های مختلف،
• پایداری یا ناپایداری در برابر هرزداده‌ها (Noises) و تغییر داده‌ها،
• سوگیری‌ها، خطاها و الگوهای تصمیم‌گیری که در اجرا ظاهر می‌شوند.

به عبارت دیگر در برنامه‌نویسی کلاسیک، رفتار تقریباً همان اجرای دقیق الگوریتم بود. اما در سیستم‌های هوش مصنوعی (AI)، رفتار الزاماً به‌طور کامل از کد قابل پیش‌بینی نیست؛ بلکه از برهم‌کنش الگوریتم، ساختار داده، و داده‌های آموزشی پدیدار می‌شود. به همین دلیل می‌گوییم در AI، «برنامه» کمتر یک متن ایستا و بیشتر یک سامانه رفتاری است که ویژگی‌هایش در اجرا و تجربه آشکار می‌شوند.

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

از دیگر سو، با درنظرگرفتن AI، این معادله حتی معنادارتر می‌شود. سامانه‌های یادگیرنده (برای مثال: OpenAI. ChatGPT / Google Gemini ai و مانند آنها) نشان می‌دهند که می‌توان رفتارهای مفید را بدون حل دقیق مسئله تولید کرد، اما هم‌زمان نظریه پیچیدگی یادآوری می‌کند که این موفقیت‌ها جایگزین حل مسائل سخت نمی‌شوند، بلکه اغلب دور زدن، تقریب‌ زدن، یا تغییر صورت مسئله هستند. بنابراین، بحث مسئله‌های سخت نه‌تنها از نظر منطقی درست است، بلکه کمک می‌کند از همان ابتدا مرز میان «آنچه می‌توان حل کرد» و «آنچه در عمل* یا در سرشت (مثل مسئله ‌NP-سخت) سخت است» را درک کنیم. این مرزی که هنوز، حتی در زمانه هوش مصنوعی، تعیین‌کننده است.

■ برخی مرجع و کتاب شناسی

Computers, Complexity, and Intractability 1
1.1 Introduction 1
1.2 Problems, Algorithms, and Complexity 4
1.3 Polynomial-Time Algorithms and Intractable Problems 6
1.4 Provably Intractable Problems 11
1.5 NP-Complete Problems 13
1.6 An Outline of the Book 14

2 The Theory of NP-Completeness 17
2.1 Decision Problems, Languages, and Encoding Schemes 18
2.2 Deterministic Turing Machines and the Class P 23
2.3 Nondeterministic Computation and the Class NP 27
2.4 The Relationship Between P and NP 32
2.5 Polynomial Transformations and NP-Completeness 34
2.6 Cook’s Theorem 38

3 Proving NP-Completeness Results 45
3.1 Six Basic NP-Complete Problems 46
3.1.1 3-SATISFIABILITY 48
3.1.2 3-DIMENSIONAL MATCHING 51
3.1.3 VERTEX COVER and CLIQUE 53
3.1.4 HAMILTONIAN CIRCUIT 56
3.1.5 PARTITION 60
3.2 Some Techniques for Proving NP-Completeness 63
3.2.1 Restriction 63
3.2.2 Local Replacement 66
3.2.3 Component Design 72
3.3 Some Suggested Exercises 74

4 Using NP-Completeness to Analyze Problems 77
5 NP-Hardness 119
6 Coping with NP-Complete Problems 121
7 Beyond NP-Completeness 153

Appendix

A List of NP-Complete Problems 187

A.1 Graph Theory 189
A.1.1 Covering and Partitioning 190
A.1.2 Subgraphs and Supergraphs 194
A.1.3 Vertex Ordering 199
A.1.4 Isomorphisms and Other Morphisms 202
A.1.5 Miscellaneous 203
A.2 Network Design 206
A.2.1 Spanning Trees 206
A.2.2 Cuts and Connectivity 209
A.2.3 Routing Problems

TRAVELING SALESMAN 211
A.2.4 Flow Problems 214
A.2.5 Miscellaneous 218
A.3 Sets and Partitions 221
A.3.1 Covering, Hitting, and Splitting 221
A.3.2 Weighted Set Problems 223
A.4 Storage and Retrieval 226
A.4.1 Data Storage 226
A.4.2 Compression and Representation 228
A.4.3 Database Problems 232

A.5 Sequencing and Scheduling 236
A.5.1 Sequencing on One Processor 236
A.5.2 Multiprocessor Scheduling 238
A.5.3 Shop Scheduling 241
A.5.4 Miscellaneous 243
A.6 Mathematical Programming 245
A.7 Algebra and Number Theory 249
A.7.1 Divisibility Problems 249
A.7.2 Solvability of Equations 250
A.7.3 Miscellaneous 252
A.8 Games and Puzzles 254
A.9 Logic 259
A.9.1 Propositional Logic 259
A.9.2 Miscellaneous 261
A.10 Automata and Language Theory 265
A.10.1 Automata Theory 265
A.10.2 Formal Languages 267
A.11 Program Optimization 272
A.11.1 Code Generation 272
A.11.2 Programs and Schemes 275
A.12 Miscellaneous 279
A.13 Open Problems 285

Symbol Index 289
Reference and Author Index 291
Subject Index 327
Update for the Current Printing 339