سد پیچیدگی P در برابر NP: چرا بررسی یک راه‌حل به‌طور تصاعدی سریع‌تر از یافتن آن است؟

یک کامپیوتر می‌تواند یک جدول سودوکوی حل‌شده را در چند میلی‌ثانیه بررسی کند و ببیند آیا هر سطر، ستون و مربع شامل اعداد ۱ تا ۹ هست یا خیر. اما یافتن همان راه‌حل از یک جدول خالی، نیازمند الگوریتمی است که در میان درخت تصاعدی و روبه‌رشدی از احتمالات جستجو کند. این عدم تقارن بنیادین — اینکه بررسی یک پاسخ به‌مراتب ساده‌تر از یافتن آن است — زیربنای مسئله P در برابر NP را تشکیل می‌دهد؛ مهم‌ترین پرسش بی‌پاسخ در علوم نظری کامپیوتر.[6]

اهمیت این مرز ریاضی بسیار فراتر از منطق انتزاعی است. اگر P (مسائلی که در زمان چندجمله‌ای قابل حل هستند) برابر با NP (مسائلی که در زمان چندجمله‌ای قابل بررسی‌اند) باشد، به این معناست که یافتن یک راه‌حل اساساً به همان سادگیِ بررسی آن است. چنین اثباتی می‌تواند پروتکل‌های رمزنگاری که امنیت بانکداری جهانی را تامین می‌کنند فرو بریزد و در عین حال، قفل بهینه‌سازی بی‌نقص را برای لجستیک، کشف دارو و هوش مصنوعی باز کند.[2]

موسسه ریاضیات کلی (Clay Mathematics Institute) در سال ۲۰۰۰ این اهمیت را رسمیت بخشید و P در برابر NP را به‌عنوان یکی از هفت «مسئله جایزه هزاره» تعیین کرد. این موسسه برای اولین اثبات درستی که این معما را حل کند، یک میلیون دلار پاداش در نظر گرفته و هسته اصلی پرسش را به‌سادگی این‌گونه بیان می‌کند: «اگر بررسی صحت راه‌حل یک مسئله آسان است، آیا حل کردن خود آن مسئله نیز آسان است؟»[1]

برای درک این سد، دانشمندان کامپیوتر وظایف محاسباتی را بر اساس نحوه مقیاس‌پذیری زمان پردازشِ مورد نیاز با بزرگ‌تر شدن ورودی، به کلاس‌های مختلفی تقسیم می‌کنند. کلاس «P» شامل مسائلی است که می‌توانند در «زمان چندجمله‌ای» حل شوند. مرتب‌سازی یک پایگاه داده با ۱۰,۰۰۰ نام یا ضرب دو عدد بزرگ در این دسته قرار می‌گیرند؛ با رشد مجموعه داده‌ها، زمان محاسباتی مورد نیاز با نرخی قابل‌مدیریت و پیش‌بینی‌پذیر افزایش می‌یابد.[2]

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

دشواری مسائل NP در انفجار تصاعدی احتمالات نهفته است. برای یک مسیر ۱۰ شهری، کامپیوتر باید ۳.۶ میلیون جایگشت را ارزیابی کند. اگر این عدد را تنها به ۲۰ شهر افزایش دهید، تعداد مسیرهای ممکن به ۱.۲۱ × ۱۰^۱۸ سر به فلک می‌کشد.

پردازنده‌ای که یک میلیارد مسیر را در ثانیه ارزیابی می‌کند، باز هم برای بررسی همه آن‌ها به ۳۸ سال زمان نیاز دارد. با این حال، اگر یک مسیر مشخص و یک مسافت هدف به همان کامپیوتر داده شود، می‌تواند در کسری از میلی‌ثانیه بررسی کند که آیا مسیر با معیارها مطابقت دارد یا خیر.[6]

فرمول‌بندی رسمی این شکاف در سال ۱۹۷۱ اتفاق افتاد؛ زمانی که پژوهشگرانی به نام‌های استیون کوک (Stephen Cook) و لئونید لوین (Leonid Levin) به‌طور مستقل مقالاتی درباره پیچیدگی رویه‌های اثبات قضیه منتشر کردند. آن‌ها نشان دادند که مجموعه خاصی از مسائل در درون NP، «NP-کامل» (NP-complete) هستند.[4]

مسائل NP-کامل مانند مترجم‌های جهانی برای پیچیدگی محاسباتی عمل می‌کنند. کوک و لوین ثابت کردند که اگر یک الگوریتم بتواند به‌سرعت یک مسئله NP-کامل را حل کند، همان الگوریتم می‌تواند برای حل سریع تمام مسائل دیگر در کلاس NP نیز تطبیق داده شود. این درهم‌تنیدگی به این معناست که یک پیشرفت غیرمنتظره در مسیریابی کامیون‌های تحویل بار، از نظر تئوری می‌تواند به یک پیشرفت بزرگ در تاخوردگی پروتئین‌ها تبدیل شود.[4]

امنیت دیجیتال مدرن کاملاً بر این فرض استوار است که P با NP برابر نیست. رمزنگاری کلید عمومی، مانند الگوریتم RSA، داده‌ها را با ضرب دو عدد اول بسیار بزرگ در یکدیگر ایمن می‌کند. عدد حاصل همان کلید عمومی است که برای رمزنگاری پیام‌ها به‌طور آشکار به اشتراک گذاشته می‌شود.[5]

در حالی که یک کامپیوتر می‌تواند دو عدد اول ۳۰۰ رقمی را در یک لحظه در هم ضرب کند، معکوس کردن این فرآیند — یعنی یافتن اعداد اول اولیه از یک حاصل‌ضرب ۶۰۰ رقمی — نیازمند جستجو در یک فضای ریاضی غیرقابل‌تصور و عظیم است. اگر P برابر با NP باشد، باید الگوریتم سریعی برای تجزیه اعداد اول وجود داشته باشد که استانداردهای فعلی رمزنگاری را یک‌شبه منسوخ می‌کند.[5]

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

در طول ۵۰ سال گذشته، جامعه علوم نظری کامپیوتر تا حد زیادی به این اجماع رسیده است که P با NP برابر نیست. پژوهشگران مرزهای نظریه پیچیدگی را به‌طور گسترده‌ای نقشه‌برداری کرده‌اند، با این حال هر تلاشی برای اثبات وجود الگوریتم‌های سریع برای مسائل NP-کامل با شکست مواجه شده است.[3]

اثبات حالت منفی — اینکه اساساً هیچ الگوریتم این‌چنینی نمی‌تواند وجود داشته باشد — نیز به همان اندازه لاینحل باقی مانده است. ریاضیدانان نشان داده‌اند که تکنیک‌های استاندارد اثبات، که به عنوان «اثبات‌های طبیعی» شناخته می‌شوند، ذاتاً قادر به حل پرسش P در برابر NP نیستند؛ به این معنی که برای تصاحب جایزه موسسه کلی، احتمالاً به شاخه کاملاً جدیدی از ریاضیات نیاز خواهد بود.[1]

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