NP-হার্ড সমস্যা চেনা — একটি প্র্যাকটিক্যাল টুলকিট
এই পাঠে যা শিখবেন
- চারটি প্র্যাকটিক্যাল সিগন্যাল যা একটি সমস্যাকে NP-হার্ড হিসেবে সন্দেহ করার ইঙ্গিত দেয়
- এই কোর্সে ইতিমধ্যে দেখা ক্লাসিক NP-হার্ড সমস্যাগুলোর একটি দ্রুত রেফারেন্স তালিকা
- পলিনোমিয়াল-টাইম রিডাকশনের ধারণা অনানুষ্ঠানিকভাবে — "সন্দেহ" থেকে "প্রমাণ" পর্যন্ত যেতে কী লাগে
- কেন "সার্চ স্পেস এক্সপোনেনশিয়াল দেখাচ্ছে" এই সিগন্যালটি একা যথেষ্ট নয়, ভুল সিদ্ধান্তে নিয়ে যেতে পারে
১ · চারটি প্র্যাকটিক্যাল সিগন্যাল
ধরুন আপনি একটি নতুন সমস্যার মুখোমুখি — কয়েকদিন চেষ্টা করেও কোনো গ্রিডি বা DP সমাধান পাচ্ছেন না, শুধু ব্রুট-ফোর্স কাজ করছে। নিচের চারটি প্রশ্ন নিজেকে জিজ্ঞেস করুন — যত বেশি "হ্যাঁ" উত্তর পাবেন, সন্দেহ তত জোরালো হবে যে সমস্যাটি NP-হার্ড।
২ · এই কোর্সে ইতিমধ্যে দেখা ক্লাসিক NP-হার্ড সমস্যা
লক্ষণীয়, এই কোর্সে আমরা ইতিমধ্যে বেশ কিছু ক্লাসিক NP-হার্ড সমস্যার মুখোমুখি হয়েছি — তখন সরাসরি ব্রুট-ফোর্স বা ব্রাঞ্চ-অ্যান্ড-বাউন্ড ব্যবহার করা হয়েছিল কারণ এদের জন্য কোনো পরিচিত পলিনোমিয়াল-টাইম সঠিক অ্যালগরিদম নেই:
দেখুন L39 — ব্রাঞ্চ-অ্যান্ড-বাউন্ড দিয়ে ছোট ইনস্ট্যান্সের জন্য এক্স্যাক্ট সমাধান।
দেখুন L25 — অপ্টিমাইজেশন ভার্সনের জন্য DP আছে, কিন্তু এর ডিসিশন ভার্সন ("মান $\ge V$ অর্জনযোগ্য কিনা") NP-complete।
দেখুন L37 — ব্যাকট্র্যাকিং দিয়ে সমাধান, কারণ কোনো পলিনোমিয়াল-টাইম কাঠামো জানা নেই।
দেখুন L47 — যাচাই সহজ, সমাধান খোঁজা কঠিন হতে পারে।
এই তালিকার বাইরেও আরও অনেক ক্লাসিক NP-কমপ্লিট সমস্যা আছে — ভার্টেক্স কভার (L51-এ এর অ্যাপ্রক্সিমেশন দেখব), সেট কভার, গ্রাফ কালারিং, ক্লিক, সাবগ্রাফ আইসোমরফিজম ইত্যাদি। এদের সম্পূর্ণ তালিকা ও প্রতিটির আনুষ্ঠানিক NP-কমপ্লিটনেস প্রমাণ (একটি নির্দিষ্ট পলিনোমিয়াল-টাইম রিডাকশনসহ) দেওয়া আছে Theory of Computation কোর্সের "More NP-Complete Problems" পাঠে।
৩ · "সন্দেহ" থেকে "প্রমাণ" পর্যন্ত — পলিনোমিয়াল-টাইম রিডাকশন, সংক্ষেপে
উপরের চেকলিস্ট শুধু একটি হিউরিস্টিক — একটি সমস্যা প্রকৃতপক্ষে NP-হার্ড তা প্রমাণ করতে একটি নির্দিষ্ট কৌশল লাগে: ইতিমধ্যে NP-কমপ্লিট বলে প্রমাণিত কোনো সমস্যা $B$ থেকে আপনার সমস্যা $A$-তে একটি পলিনোমিয়াল-টাইম রিডাকশন $B \le_p A$ দেখানো — অর্থাৎ $B$-এর যেকোনো ইনস্ট্যান্সকে পলিনোমিয়াল সময়ে $A$-এর একটি ইনস্ট্যান্সে রূপান্তর করা যায় এমনভাবে যে দুটোর উত্তর একই হয়। এই রূপান্তর কৌশল ও এর পেছনের যুক্তি সম্পূর্ণভাবে আনুষ্ঠানিকভাবে "Polynomial-Time Reductions and NP-Completeness" পাঠে কভার করা হয়েছে, আর এই পুরো ভিতের প্রথম "বেস কেস" — যে কোনো NP সমস্যাকেই SAT-তে রিডিউস করা যায় — তা প্রমাণ করে বিখ্যাত Cook-Levin থিওরেম। এই কোর্সে আমরা এই আনুষ্ঠানিক রিডাকশন মেশিনারি পুনরায় তৈরি করব না — শুধু জানব এটি বিদ্যমান এবং কোথায় খুঁজতে হবে।
সিগন্যাল ২ (এক্সপোনেনশিয়াল সার্চ স্পেস) সম্পর্কে একটা সতর্কতা জরুরি — শুধু ব্রুট-ফোর্স সমাধান এক্সপোনেনশিয়াল দেখানো মানেই সমস্যাটি NP-হার্ড নয়। এই কোর্সেরই M6-এ দেখেছি, নেইভ রিকার্সিভ ফিবোনাচি (L10) বা LCS-এর নেইভ রিকার্সন (L26) দেখতে এক্সপোনেনশিয়াল মনে হয়, কিন্তু ওভারল্যাপিং সাবপ্রবলেম চিনে DP দিয়ে পলিনোমিয়াল সময়ে সমাধান করা যায় — এরা মোটেও NP-হার্ড নয়! তাই সিগন্যাল ২ একা যথেষ্ট নয়; সিগন্যাল ৩ (গ্রিডি/DP প্রমাণ করার আন্তরিক চেষ্টা ব্যর্থ হওয়া) এবং সিগন্যাল ১/৪ (পরিচিত সমস্যার সাথে মিল) একসাথে দেখাই বেশি নির্ভরযোগ্য।
নিচের কোড সেলে দেখা যাক এক্সপোনেনশিয়াল ও ফ্যাক্টোরিয়াল গ্রোথ ঠিক কতটা দ্রুত পলিনোমিয়াল গ্রোথকে ছাড়িয়ে যায় — এটাই সিগন্যাল ২-এর "দেখতে এক্সপোনেনশিয়াল" ধারণাটাকে সংখ্যায় concrete করে তোলে।
import math
print(f"{'n':>3} | {'n^3 (পলিনোমিয়াল)':>20} | {'2^n (এক্সপোনেনশিয়াল)':>24} | {'n! (ফ্যাক্টোরিয়াল)':>22}")
for n in [5, 10, 15, 20, 25, 30]:
poly = n ** 3
exp = 2 ** n
fact = math.factorial(n)
print(f"{n:>3} | {poly:>20,} | {exp:>24,} | {fact:>22,}")এই চেকলিস্ট একটি প্রফেশনাল অ্যালগরিদম ডিজাইনারের ব্যবহারিক অভিজ্ঞতা-ভিত্তিক টুল — কখন একটি পলিনোমিয়াল-টাইম সঠিক সমাধান খোঁজা বন্ধ করে বিকল্প কৌশলে (এক্স্যাক্ট এক্সপোনেনশিয়াল পদ্ধতি, অ্যাপ্রক্সিমেশন, বা হিউরিস্টিক) সরে যাওয়া উচিত তা দ্রুত সিদ্ধান্ত নিতে সাহায্য করে। এই সিদ্ধান্তের পরের ধাপ — অর্থাৎ NP-হার্ডনেসের মুখোমুখি হলে ঠিক কী করণীয় — তাই পরের পাঠ L49-এর বিষয়।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ যদি একটি সমস্যা উপরের চেকলিস্টের সবগুলো সিগন্যাল দেখায়, তাহলে কি এটি নিশ্চিতভাবে NP-হার্ড প্রমাণিত হয়ে গেল?
না। এই চেকলিস্ট একটি হিউরিস্টিক, আনুষ্ঠানিক প্রমাণ নয়। একটি সমস্যা প্রকৃতপক্ষে NP-হার্ড তা প্রমাণ করতে একটি নির্দিষ্ট, ইতিমধ্যে NP-কমপ্লিট বলে প্রমাণিত সমস্যা থেকে একটি প্রকৃত পলিনোমিয়াল-টাইম রিডাকশন দেখাতে হয় — এই মেশিনারি Theory of Computation কোর্সের L45-L47-এ পূর্ণাঙ্গভাবে কভার করা হয়েছে। চেকলিস্টটা শুধু আপনাকে বলে দেয় কখন এই পথে যাওয়ার (বা বিকল্প কৌশল খোঁজার) চেষ্টা করা যুক্তিসঙ্গত।
প্র ০২ L22-এর ফ্র্যাকশনাল ন্যাপস্যাক গ্রিডি দিয়ে অপটিমালভাবে সমাধান করা যায়, কিন্তু 0/1 ন্যাপস্যাকের ডিসিশন ভার্সন কেন NP-complete বলে ধরা হয়?
ফ্র্যাকশনাল ভার্সনে আইটেম ভাগ করা যায় বলে ভ্যালু/ওয়েট রেশিও অনুযায়ী গ্রিডি চয়েসের জন্য একটি বৈধ এক্সচেঞ্জ আর্গুমেন্ট আছে (L19-L22)। 0/1 ভার্সনে আইটেম আস্ত নিতে হবে বা বাদ দিতে হবে — এই সীমাবদ্ধতা এক্সচেঞ্জ আর্গুমেন্টকে ভেঙে দেয় (একটি বেশি রেশিওর আইটেম সবসময় নেওয়া optimal নাও হতে পারে, ওজনের সীমাবদ্ধতার কারণে)। 0/1 ন্যাপস্যাকের ডিসিশন ভার্সন ("$W$ ওজনের মধ্যে $\ge V$ মান অর্জনযোগ্য কিনা") আসলে Karp-এর মূল ২১টি NP-complete সমস্যার একটি — যদিও এর অপ্টিমাইজেশন ভার্সনের জন্য L25-এ একটি সিউডো-পলিনোমিয়াল DP আছে (যা $W$-এর মানের উপর নির্ভরশীল, ইনপুটের বিট-লেংথের উপর সত্যিকারের পলিনোমিয়াল নয়)।
প্র ০৩ কেন শুধু "সার্চ স্পেস এক্সপোনেনশিয়াল দেখাচ্ছে" (সিগন্যাল ২) দেখেই একটি সমস্যাকে NP-হার্ড ধরে নেওয়া বিপজ্জনক হতে পারে?
কারণ অনেক সমস্যার নেইভ/ব্রুট-ফোর্স সমাধান এক্সপোনেনশিয়াল দেখায়, কিন্তু গভীরে একটা পলিনোমিয়াল কাঠামো (ওভারল্যাপিং সাবপ্রবলেম বা গ্রিডি-চয়েস প্রপার্টি) লুকিয়ে থাকে — যেমন নেইভ রিকার্সিভ ফিবোনাচি (L10) বা LCS-এর নেইভ রিকার্সন (L26), দুটোই দেখতে $O(2^n)$ কিন্তু DP দিয়ে পলিনোমিয়াল সময়ে সমাধানযোগ্য। তাই সিগন্যাল ২ শুধু একটি প্রাথমিক ইঙ্গিত — সিদ্ধান্তে পৌঁছানোর আগে গ্রিডি ও DP-এর মতো টেকনিক আন্তরিকভাবে চেষ্টা করা উচিত (সিগন্যাল ৩)।
অনুশীলন
-
চিন্তা করুন: L26-এর লংগেস্ট কমন সাবসিকোয়েন্স সমস্যার নেইভ রিকার্সিভ সমাধান এক্সপোনেনশিয়াল
(সিগন্যাল ২ পূরণ করে)। তাহলে কি এই সমস্যাটি উপরের চেকলিস্ট অনুযায়ী NP-হার্ড বলে সন্দেহ করা উচিত?
না। শুধু সিগন্যাল ২ পূরণ হলেই যথেষ্ট নয় — সিগন্যাল ৩ পরীক্ষা করলে দেখা যায় LCS-এর একটি সুস্পষ্ট অপটিমাল সাবস্ট্রাকচার আছে এবং একটি পলিনোমিয়াল-সময়ের DP সমাধান (L26) বিদ্যমান। তাই সিগন্যাল ২ একা থাকলেও সিগন্যাল ৩ ব্যর্থ না হওয়া পর্যন্ত (অর্থাৎ DP/গ্রিডি সত্যিই কাজ না করা পর্যন্ত) সন্দেহ জোরালো হয় না।
-
পরীক্ষা করুন: কোড সেলের
[5, 10, 15, 20, 25, 30]লিস্টে35যোগ করে Run চেপে দেখুন $n^3$, $2^n$, এবং $n!$-এর মধ্যে পার্থক্য কতটা আরও বেড়ে যায়।$n=35$-এ $n^3 = 42{,}875$ (এখনও ছোট), $2^n$ প্রায় $৩৪৩৬$ কোটি, আর $n!$ প্রায় $10^{40}$ ছাড়িয়ে যায় — পলিনোমিয়াল কলামের সাথে অন্য দুই কলামের ব্যবধান প্রতিটি ধাপে দ্রুত বাড়তে থাকে, এটাই "এক্সপোনেনশিয়াল বনাম পলিনোমিয়াল গ্রোথ"-এর ব্যবহারিক চেহারা।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- Theory of Computation: "More NP-Complete Problems" সম্পূর্ণ ক্যাটালগ ভার্টেক্স কভার, গ্রাফ কালারিং, সেট কভার-সহ ক্লাসিক NP-কমপ্লিট সমস্যার তালিকা ও তাদের রিডাকশন প্রমাণ।
- Theory of Computation: "Polynomial-Time Reductions and NP-Completeness" রিডাকশন মেশিনারি আনুষ্ঠানিক প্রমাণের জন্য প্রয়োজনীয় পলিনোমিয়াল-টাইম রিডাকশন কীভাবে তৈরি ও যাচাই করতে হয়।
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৫৭টি পাঠ পরের পাঠে NP-হার্ডনেসের মুখোমুখি হলে ঠিক কী করণীয় — এক্স্যাক্ট, অ্যাপ্রক্সিমেট নাকি হিউরিস্টিক — তার সিদ্ধান্ত-কাঠামো দেখব।