وقتی یک 1 گران‌تر از یک 0 تمام می‌شود، فشرده‌سازی دشوار می‌شود

برای ذخیره یا ارسال فشردهٔ یک متن، به هر نماد واژه‌ای ساخته‌شده از 0 و 1 بدهید، کوتاه برای نمادهای پرتکرار و بلندتر برای نمادهای کمیاب. این واژه‌ها باید یک کد پیشوندی (prefix code) تشکیل دهند: هیچ واژه‌ای نباید آغاز واژهٔ دیگری باشد. {0, 10, 11} درست است؛ {0, 01, 11} نه، چون 01 با 0 آغاز می‌شود. با یک کد پیشوندی، رشته‌ای بلند از بیت‌ها را می‌توان بدون هیچ جداکننده‌ای دوباره به واژه‌ها برید.

بهترین کد از این دست — کدی با کمترین طول میانگین — در سال 1952 به دست دی. اِی. هافمن (D. A. Huffman) یافته شد، با دستورالعملی حریصانه (greedy) و ساده که سریع اجرا می‌شود.

وقتی حروف بها دارند

دستورالعمل هافمن فرض می‌کند که یک 0 و یک 1 هزینهٔ یکسانی دارند. فرض کنید چنین نباشد: ارسال 1 زمان بیشتری می‌برد، یا ذخیره‌اش جای بیشتری می‌گیرد. اکنون هزینهٔ هر واژه مجموع هزینهٔ حروف آن است، و ترکیب یک واژه به اندازهٔ طولش اهمیت دارد. برای نمونه، با هزینه‌های 1 و 3، واژه‌های 00 و 01 هم‌طول‌اند اما هزینه‌شان 2 و 4 است.

این گونه از مسئله پیشینه‌ای طولانی دارد. آر. ام. کارپ (R. M. Karp) در سال 1961 آن را به صورت یک مسئلهٔ برنامه‌ریزی عدد صحیح نوشت. پژوهش‌های بعدی الگوریتم‌هایی دقیق و کارآمد برای هر جفت ثابتی از هزینه‌های صحیح یافتند، و نیز یک طرح تقریبی که به هر اندازهٔ دلخواه به بهینه نزدیک می‌شود. اما وقتی خود هزینه‌ها بخشی از ورودی باشند، هیچ‌کس نمی‌دانست مسئله چقدر دشوار است. حتی در سال 2021، این مسئله هنوز در فهرست مسائل باز بود.

پاسخ: NP-کامل

ال. سونیل چاندران (L. Sunil Chandran)، از مؤسسهٔ علوم هند (Indian Institute of Science) در بنگلور، و ریشیکش گاجالا (Rishikesh Gajjala)، از Pramaana Labs، اکنون ثابت می‌کنند که تصمیم‌گیری دربارهٔ اینکه آیا کدی با هزینهٔ حداکثر K وجود دارد یا نه، NP-کامل (NP-complete) است — حتی وقتی دو هزینه عددهای صحیح متوالی M و M + 1 باشند. دانشمندان علوم رایانه مسئله‌ای را NP-کامل می‌نامند که به اندازهٔ یک خانوادهٔ کامل از مسائل کلاسیک دشوار باشد: یک روش کلی و سریع برای یکی از آن‌ها، روشی برای همه به دست می‌داد، و هیچ روشی از این دست شناخته نشده است. بنابراین یافتن ارزان‌ترین کد NP-سخت (NP-hard) است.

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

معمایی پنهان در یک درخت کدگذاری

اثبات از یک مسئلهٔ دشوار شناخته‌شده آغاز می‌شود: در شبکه‌ای که بی‌هیچ تقاطعی روی یک برگه کشیده شده است، آیا می‌توان k نقطه برگزید که هیچ دوتایی از آن‌ها به هم وصل نباشند؟ سپس مسئله‌ای در کدگذاری می‌سازد که ارزان‌ترین کدش به آن پرسش پاسخ می‌دهد.

1. هر کد پیشوندی یک درخت است: 0 به چپ می‌رود، 1 به راست. وقتی هزینهٔ حروف M و M + 1 باشد، واژه‌ای به عمق d با z رقم 1، هزینه‌ای برابر M × d + z دارد. عمق بخش بزرگ هزینه را تعیین می‌کند، و شمار 1ها بخش کوچک آن را.
2. نویسندگان مسئلهٔ میانی تازه‌ای طراحی می‌کنند: تعیین کنید درخت در هر عمق چند برگ دارد، و به جایگاه برگ‌هایش امتیاز دهید. آن‌ها نشان می‌دهند که یک درخت ارزان باید، در حالی که تراز به تراز رشد می‌کند، برنامهٔ کوچکی را اجرا کند که نقاط برگزیده را یکی‌یکی بررسی می‌کند، هر انتخاب را رونوشت می‌کند و هر پیوند را می‌آزماید. هر میان‌بُری دست‌کم یک واحد بیشتر هزینه دارد؛ هر نقطهٔ برگزیده دقیقاً یک واحد صرفه‌جویی می‌کند.
3. سرانجام، بسامدها چنان تنظیم می‌شوند که هر نماد ناگزیر به عمق درست برود، و امتیاز برابر با هزینهٔ کدگذاری به‌اضافهٔ مقداری ثابت شود.

نمونهٔ کوچکی از مقاله نشان می‌دهد هزینه‌ها چقدر ظریف‌اند. سه نماد بسامدهای 20، 12 و 9 دارند، و هزینهٔ حروف 83 و 84 است. کد (0, 10, 11) هزینه‌ای برابر 5,176 دارد. کد (1, 00, 01) هزینه‌ای برابر 5,175 دارد: سپردن حرف گران‌تر به پرتکرارترین نماد برنده است، چون آنگاه دو واژهٔ دیگر 1های کمتری دارند.

دشواری کجا پنهان است

نتیجهٔ دوم سرچشمهٔ دشواری را در دل کدگذاری معمولی می‌یابد. دستورالعمل هافمن کوتاه‌ترین طول میانگین را به‌سرعت پیدا می‌کند. اما از میان همهٔ کدهایی که به آن طول می‌رسند، برگزیدن کدی با کمترین شمار 1ها، وزن‌دهی‌شده با بسامد، نیز NP-کامل است.

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

اثباتی یافته‌شده با هوش مصنوعی

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