P vs NP: কম্পিউটার সায়েন্সের সবচেয়ে দামী রহস্য

আচ্ছা, একটা মজার প্রশ্ন দিয়ে শুরু করি। ধরো তোমাকে বলা হলো "৫০টা শহরে ডেলিভারি দিতে হবে, এমন একটা রুট বের করো যেখানে টোটাল দূরত্ব সবচেয়ে কম হয়।" শুনতে সহজ লাগছে? এখন চেষ্টা করে দেখো। ৫০টা শহরের জন্য possible রুট সংখ্যা প্রায় ৩০৪৪১৪০৯১১৫৪২৭৪১৯৩২৩২৬৭০৪৪৫২৬২৫৭৫২১১৯৯৯০০৫২৯৪৩২১৯৫৯৯৪৪৯৬৯৫৭৭২৫৪৫২৪১৩৮৬৫৪৩৫৯৫৮৪৬৪৩... থামো, এত বড় সংখ্যা লেখারই দরকার নেই। এটা এত বিশাল যে পৃথিবীর সবচেয়ে শক্তিশালী সুপারকম্পিউটারও ব্রুট-ফোর্স করতে গেলে মহাবিশ্বের বয়সের চেয়েও বেশি সময় লাগিয়ে ফেলবে।

মজার ব্যাপার হলো এই ধরনের "অসম্ভব কঠিন" মনে হওয়া প্রবলেমগুলোর একটা কমন প্যাটার্ন আছে, আর কম্পিউটার সায়েন্টিস্টরা এই প্যাটার্নটাকে নাম দিয়েছেন NP। আর এই ক্যাটাগরির প্রবলেম নিয়ে এমন একটা প্রশ্ন আছে যেটার উত্তর দিতে পারলে তুমি রাতারাতি বিলিয়নিয়ার আর কম্পিউটার সায়েন্সের ইতিহাসে আইনস্টাইনের কাতারে চলে যাবে। কারণ Clay Mathematics Institute এই প্রশ্নের সমাধানের জন্য ঘোষণা দিয়ে রেখেছে ১০ লক্ষ ডলার।

চলো বুঝি জিনিসটা আসলে কী।

টুরিং মেশিন — অ্যালগোরিদমের "থট এক্সপেরিমেন্ট"

১৯৩৬ সালে অ্যালান টুরিং একটা কাল্পনিক মেশিন ডিজাইন করলেন। বাস্তবে বানাননি, শুধু কাগজে-কলমে থিওরি দিয়েছিলেন। উদ্দেশ্য ছিল একটাই প্রশ্নের উত্তর খোঁজা: "একটা প্রবলেম যদি সলভ করা সম্ভব হয়, তাহলে সেটা ঠিক কীভাবে সলভ হয়?"

তার মেশিনে ছিল একটা অসীম লম্বা টেপ আর একটা হেড যেটা টেপের উপর দিয়ে চলাচল করে, প্রতিটা ধাপে একটা "স্টেট" পরিবর্তন করে। কোন স্টেট থেকে কোন স্টেটে যাওয়া যাবে সেটা আগে থেকে ঠিক করা নিয়ম (transition rules) দিয়ে নির্ধারিত। মজার ব্যাপার হলো, আজকের তোমার ল্যাপটপ, স্মার্টফোন, এমনকি ChatGPT চালানো বিশাল সার্ভার সবকিছুই মূলত এই সাধারণ আইডিয়ারই এক বিশাল, দ্রুতগতির ভার্সন। যা কিছু টুরিং মেশিন দিয়ে সলভ করা যায় না, তা কম্পিউটার দিয়েও সলভ করা যায় না। এখনও পর্যন্ত এটাই কম্পিউটেবিলিটির সীমারেখা।

ডিটারমিনিস্টিক মেশিনে প্রতিটা অবস্থায় করণীয় ঠিক একটাই পথ থাকে। যেমন GPS নেভিগেশন, একটা নির্দিষ্ট ইনপুটে সবসময় একই আউটপুট। কিন্তু নন-ডিটারমিনিস্টিক মেশিনের ক্ষেত্রে একই অবস্থায় একাধিক সম্ভাব্য পথ থাকতে পারে, আর মেশিনটা যেন "জাদুকরী অনুমান" (lucky guess) করে সঠিক পথ বেছে নেয়। বাস্তবে এমন মেশিন নেই, এটা শুধুই একটা তাত্ত্বিক টুল যা দিয়ে আমরা প্রবলেমের কাঠিন্য মাপি।

P: যেসব প্রবলেম আমাদের হাতের মুঠোয়

P (Polynomial) ক্যাটাগরির প্রবলেমগুলো ডিটারমিনিস্টিক মেশিন দিয়ে পলিনমিয়াল টাইমে (O(n), O(n log n), O(n³), অর্থাৎ ইনপুট বাড়লেও সময় বাড়ে "যুক্তিসঙ্গত হারে") সলভ করা যায়। শর্টেস্ট পাথ বের করা, একটা লিস্ট সর্ট করা। এসব P প্রবলেম।

এখানে একটা গুরুত্বপূর্ণ ধারণা হলো সার্টিফিকেট। ধরো, কেউ তোমাকে একটা "উত্তর" দিলো. তুমি কি সেটা ঝটপট চেক করতে পারবে যে উত্তরটা সঠিক কি না? যেমন ইউলার পাথ প্রবলেমে (গ্রাফের প্রতিটা এজ ঠিক একবার ভিজিট করতে হবে) কেউ একটা রুট দিলে তুমি এজ ধরে ধরে হেঁটে সহজেই ভেরিফাই করতে পারবে সেটা ভ্যালিড কি না। P প্রবলেমের বৈশিষ্ট্য হলো শুধু সলভ করাই না, একটা প্রস্তাবিত উত্তর ভেরিফাই করাও পলিনমিয়াল টাইমে সম্ভব।

NP: যেসব প্রবলেম চেক করা সহজ, বানানো কঠিন

এবার আসল মজা। NP (Non-deterministic Polynomial) প্রবলেমের ক্ষেত্রে একটা প্রস্তাবিত উত্তর পলিনমিয়াল টাইমে ভেরিফাই করা যায়, কিন্তু সেই উত্তরটা প্রথম থেকে খুঁজে বের করা পলিনমিয়াল টাইমে সম্ভব কি না সেটা কেউ প্রমাণ করতে পারেনি।

উদাহরণঃ সুডোকু! একটা পূরণ করা সুডোকু বোর্ড দিলে তুমি সেকেন্ডেই চেক করতে পারবে এটা ঠিক আছে কি না (প্রতিটা সারি, কলাম, বক্সে ১-৯ একবার করে আছে কি না)। কিন্তু খালি বোর্ড থেকে সলিউশন বের করা? বোর্ড যত বড় হবে, ততই কঠিন হতে থাকবে। কোনো শর্টকাট নেই, ব্রুট-ফোর্স আর ব্যাকট্র্যাকিং ছাড়া উপায় নেই।

আরেকটা ক্লাসিক উদাহরণ হ্যামিল্টনিয়ান পাথ। একটা গ্রাফের সবগুলো নোড ঠিক একবার ভিজিট করে এমন একটা পথ আছে কি না। পলিনমিয়াল সলিউশন এখনও কেউ বের করতে পারেনি। যা আছে তা এক্সপোনেনশিয়াল কমপ্লেক্সিটির (O(2ⁿ) টাইপ), যেগুলো ইনপুট একটু বড় হলেই কম্পিউটারকে হাঁপিয়ে তোলে।

এক ট্রিলিয়ন ডলারের প্রশ্ন: P = NP?

প্রতিটা P প্রবলেমই আসলে NP-এর একটা সদস্য (কারণ সলভ করা গেলে ভেরিফাই তো করাই যাবে)। প্রশ্ন হলো উল্টোটা, প্রতিটা NP প্রবলেমকেই কি P-তে ফেলা সম্ভব? অর্থাৎ, যা কিছু ভেরিফাই করা সহজ, তা কি খুঁজে বের করাও সহজ হবে একদিন?

এখানেই ব্যাপারটা "current era"-তে ভয়ংকর গুরুত্বপূর্ণ হয়ে ওঠে। তোমার ব্যাংক অ্যাকাউন্ট, WhatsApp-এর এন্ড-টু-এন্ড এনক্রিপশন, ব্লকচেইনের সিকিউরিটি সবকিছুর ভিত্তি হলো এমন কিছু গাণিতিক প্রবলেম (যেমন বড় সংখ্যাকে ফ্যাক্টরাইজ করা) যা ভেঙে ফেলা (crack করা) কঠিন, কিন্তু ভেরিফাই করা সহজ। যদি কোনোদিন প্রমাণ হয় P = NP, তাহলে আজকের পুরো ইন্টারনেট সিকিউরিটি ইনফ্রাস্ট্রাকচার তাসের ঘরের মতো ভেঙে পড়বে। কারণ যেকোনো এনক্রিপশন "ভেরিফাই করা সহজ" এই নীতির উপর দাঁড়িয়ে, আর সেটাই যদি "সলভ করাও সহজ" হয়ে যায়, তাহলে কারো কোনো গোপনীয়তা আর অক্ষত থাকবে না।

তবে বেশিরভাগ কম্পিউটার সায়েন্টিস্ট মনে করেন P ≠ NP। কিন্তু "মনে করা" আর "প্রমাণ করা" এক জিনিস নয়। আইনস্টাইন মুখে যা-ই ভাবুন না কেন, পিয়ার-রিভিউড প্রমাণ ছাড়া সেটা বিজ্ঞান নয়।

NP-hard এবং NP-complete: কাজিন প্রবলেমদের পরিবার

একটা প্রবলেমকে NP-hard বলা হয় যদি সেটা "অন্তত NP-এর যেকোনো প্রবলেমের মতোই কঠিন" হয়। এমনকি সেটা নিজে NP-এর মধ্যেও নাও পড়তে পারে (মানে ভেরিফাই করাও কঠিন হতে পারে)। এই কাঠিন্য প্রমাণ করা হয় রিডাকশন দিয়ে। একটা পরিচিত কঠিন প্রবলেমকে পলিনমিয়াল টাইমে নতুন প্রবলেমে রূপান্তর করে দেখানো যে "যদি নতুনটা সহজে সলভ করা যেত, তাহলে পুরনোটাও যেত।"

আর যে প্রবলেম NP-hard এবং NP দুটোতেই পড়ে, সেটা NP-complete। এই ক্যাটাগরির সবচেয়ে বিখ্যাত উদাহরণ হলো Boolean Satisfiability (SAT) প্রবলেম। কিছু বুলিয়ান ভ্যারিয়েবল আর শর্ত দেওয়া থাকলে, এমন true/false অ্যাসাইনমেন্ট আছে কি না যাতে সব শর্ত সত্যি হয়। ১৯৭১ সালে Stephen Cook (আর স্বতন্ত্রভাবে Leonid Levin) প্রমাণ করেন SAT-ই প্রথম প্রমাণিত NP-complete প্রবলেম। এই কাজের জন্য Cook পরে কম্পিউটার সায়েন্সের সর্বোচ্চ সম্মান টুরিং অ্যাওয়ার্ড পান।

এখানেই আসল টুইস্ট NP-complete প্রবলেমগুলো একে অপরের সাথে "কনভার্টেবল"। মানে তুমি যদি এদের যেকোনো একটা পলিনমিয়াল টাইমে সলভ করে ফেলো, তাহলে বাকি সবগুলোও (ট্রাভেলিং সেলসম্যান, গ্রাফ কালারিং, নলেজ্যাক...) নিমেষে সলভ হয়ে যাবে একই টেকনিক দিয়ে। এই একটা কারণেই এই প্রবলেমগুলোর গুরুত্ব এত বেশি।

যখন সলভ করাও যায় না, ভেরিফাইও যায় না

আরেকটা মজার কেস আছে হল্টিং প্রবলেম। একটা প্রোগ্রাম দেখে বলতে হবে এটা কখনো থামবে নাকি অসীম লুপে আটকে থাকবে। এলান টুরিং নিজেই প্রমাণ করেছিলেন এটা কোনোভাবেই সমাধানযোগ্য নয়। না পলিনমিয়াল টাইমে, না কোনো সময়েই। এমনকি আজকের সবচেয়ে অ্যাডভান্সড AI মডেলও একটা র‍্যান্ডম প্রোগ্রামকে দেখে ১০০% নিশ্চিতভাবে বলতে পারবে না এটা infinite loop-এ পড়বে কি না। এটা গাণিতিকভাবেই অসম্ভব।

তাহলে প্র‍্যাক্টিক্যালি আমরা কী করি?

যেহেতু পলিনমিয়াল সলিউশন নেই, বাস্তব জীবনে ইঞ্জিনিয়াররা এক্সপোনেনশিয়াল অ্যালগোরিদমকেই যতটা সম্ভব স্মার্ট বানানোর চেষ্টা করেন। ব্রাঞ্চ অ্যান্ড বাউন্ড, হিউরিস্টিক, আর আজকাল তো AI/মেশিন লার্নিং বেসড অপ্টিমাইজেশন দিয়ে সার্চ স্পেস কমিয়ে ফেলা হয়। উবার, গুগল ম্যাপস, ডেলিভারি কোম্পানিগুলো রুট অপ্টিমাইজেশনের মতো NP-hard প্রবলেম প্রতিদিন লাখো বার সলভ করছে। Perfect সলিউশন না পেলেও, "যথেষ্ট ভালো" সলিউশন সেকেন্ডে বের করে ফেলছে।

প্রোগ্রামিং কনটেস্টেও প্রায়ই NP প্রবলেম দেখা যায়, তবে সেখানে ইনপুট সাইজ ছোট রাখা হয় যাতে ব্যাকট্র্যাকিং দিয়ে ৩-১০ সেকেন্ডেই সলভ করা যায়।

আর কোয়ান্টাম কম্পিউটিং নিয়ে যতই হাইপ থাকুক না কেন এখন পর্যন্ত এটাও প্রমাণিত নয় যে কোয়ান্টাম কম্পিউটার NP-complete প্রবলেম পলিনমিয়াল টাইমে সলভ করতে পারবে। তাই P vs NP রহস্য এখনও অক্ষত, আর ১০ লক্ষ ডলারও কারো হাতে ওঠেনি।

শেষ কথা

তাহলে পরের বার যখন কেউ বলবে "এটা তো NP-hard প্রবলেম, সলভ করা অসম্ভব!" তুমি জানবে আসলে ঠিক কী বলা হচ্ছে। আর যদি সত্যিই কোনোদিন P = NP প্রমাণ করে ফেলতে পারো, শুধু ১০ লক্ষ ডলারই না, তুমি পুরো ইন্টারনেট সিকিউরিটি, ক্রিপ্টোগ্রাফি, আর কম্পিউটার সায়েন্সের ইতিহাস সবকিছু নতুন করে লিখে ফেলবে।