✖

কম্পিউটার বিজ্ঞানের সবচেয়ে বড় সমস্যা: P বনাম NP

গণিতের এমন সাতটি সমস্যা আছে, যেগুলোকে এত কঠিন ও আকর্ষণীয় মনে করা হয় যে ক্লে ম্যাথমেটিক্স ইনস্টিটিউট এদের নাম দিয়েছে সহস্রাব্দ সমস্যা (Millennium Prize Problems)। এদের যেকোনো একটির সমাধান করলে সমাধানকারী পাবেন দশ লাখ ডলার পুরস্কার। এর একটি সমস্যা কম্পিউটার বিজ্ঞানের সঙ্গেও জড়িত, এর নাম P বনাম NP সমস্যা। চল, দেখি সমস্যাটি আসলে কী নিয়ে।

সত্যি বলতে, নিজেকে ফাঁকি দিয়ে লাভ নেই, এটা বুঝিয়ে বলা সহজ হবে না। হাজার হোক, এটা একটা সহস্রাব্দ সমস্যা। তাই এক কাপ ভালো সবুজ চা 🍵 বানিয়ে নাও, তারপর শুরু করি। প্রথমে আমরা কম্পিউটার বিজ্ঞান ও অ্যালগরিদমের জগৎ থেকে চারটি ভিন্ন সমস্যা দেখব। সমস্যাগুলো বিশ্লেষণ করে দেখব, P ও NP অক্ষরগুলোর সঙ্গে এদের সম্পর্ক কী।

সমস্যা 1: সবচেয়ে ছোট সংখ্যা খোঁজা

P বনাম NP সমস্যা অ্যালগরিদম ও তাদের জটিলতা নিয়ে। কল্পনা কর, আমি তোমার সামনে একশটি কাগজের টুকরো ঢেলে দিলাম, প্রতিটিতে একটি করে সংখ্যা লেখা। আমি চাই, তুমি সেই কাগজটি খুঁজে বের কর, যেটিতে সবচেয়ে ছোট সংখ্যাটি লেখা। এতে তোমার কত সময় লাগবে?

আধা মিনিট? দুই মিনিট?

তাত্ত্বিক কম্পিউটার বিজ্ঞানে সময়ের এই এককগুলো নিয়ে আমাদের তেমন মাথাব্যথা নেই। আমাদের আগ্রহ বরং প্রক্রিয়ার সংখ্যায়। তাই প্রশ্নটি একটু অন্যভাবে করা যায়: সবচেয়ে ছোট সংখ্যাটি পেয়েছি, এ ব্যাপারে নিশ্চিত হতে আমাকে কয়টি কাগজ পরীক্ষা করতে হবে? উত্তর হলো, সব কাগজই পরীক্ষা করতে হবে, কারণ সবচেয়ে ছোট সংখ্যাটি একেবারে শেষ কাগজেও থাকতে পারে। তোমার সামনে একশটি কাগজ ফেললে তোমাকে একশটি কাগজই পরীক্ষা করতে হবে। এক হাজারটি ফেললে পরীক্ষা করতে হবে এক হাজারটি। সাধারণভাবে, তোমার সামনে n টি কাগজ ফেললে তোমাকে n টি কাগজ পরীক্ষা করতে হবে।

একেই আমরা বলি অ্যালগরিদমের জটিলতা। তোমার সামনে n টি কাগজ ফেললে সবচেয়ে ছোট সংখ্যাটি খুঁজে পেতে যদি তোমাকে n টি প্রক্রিয়া করতে হয়, তার মানে সবচেয়ে ছোট সংখ্যা খোঁজার এই অ্যালগরিদমের জটিলতা n। একে রৈখিক জটিলতাও বলা হয়, কারণ জটিলতাটি একটি রৈখিক ফাংশন দিয়ে প্রকাশ করা যায়।

বেশ, তুমি একশটি কাগজ দেখে ঘোষণা করলে যে সবচেয়ে ছোট সংখ্যা 17। তুমি সত্যি বলছ কি না, তা আমি কীভাবে যাচাই করব? আবার সব কাগজ দেখে কোনোটিতে এর চেয়ে ছোট সংখ্যা নেই, তা পরীক্ষা করা ছাড়া অন্য কোনো উপায় নেই। অর্থাৎ সবচেয়ে ছোট সংখ্যাটি খুঁজে পেতে তোমাকে n টি কাগজ দেখতে হয়, আর আমি যাচাই করতে চাইলে আমাকেও একই কাজ করতে হয়। তাই ফলাফল যাচাইয়ের জটিলতাও n, রৈখিক জটিলতা।

এমন কোনো অ্যালগরিদম কি আছে, যার ফলাফল খুঁজে বের করার চেয়ে যাচাই করা সহজ?

সমস্যা 2: জোড়ার গুণফল

কল্পনা কর, আমি তোমার সামনে সমান আকারের দুইটি কাগজের স্তূপ ঢেলে দিলাম, প্রতিটি কাগজে আবারও একটি করে সংখ্যা। এবার আমি চাই, তুমি স্তূপ A থেকে একটি সংখ্যা আর স্তূপ B থেকে একটি সংখ্যা এমনভাবে খুঁজে বের কর, যেন তাদের গুণফল 918 হয়। উদাহরণ হিসেবে ধরি, সংখ্যার স্তূপ দুইটি এরকম:

A={49,11,32,54,15}B={17,64,74,61,21}

কীভাবে এমন একজোড়া সংখ্যা খুঁজে পাব, যাদের গুণফল 918? সোজা কথা, সব সম্ভাবনা পরীক্ষা করে দেখতে পারি। এরকম কয়টি সম্ভাবনা আছে? বেশ অনেকগুলো, মোট 25 টি। শুরুতে স্তূপ A এর প্রথম সংখ্যা, অর্থাৎ 49 কে স্তূপ B এর প্রতিটি সংখ্যা দিয়ে গুণ করি:

49⋅17=83349⋅64=313649⋅74=362649⋅61=298949⋅21=1029

কোনো জোড়া থেকেই 918 আসেনি। তাই স্তূপ A এর বাকি সংখ্যাগুলো নিয়ে একই কাজ করি, অর্থাৎ 11 এর জন্য আরও পাঁচটি জোড়া, 32 এর জন্য আরও পাঁচটি, 54 এর জন্য আরও পাঁচটি, আর 15 এর জন্য শেষ পাঁচটি জোড়া। সব মিলিয়ে 25 জোড়া সংখ্যা পরীক্ষা করা যায়। শেষে দেখা যায়, 54 · 17 = 918।

এই অ্যালগরিদমের জটিলতা কত? আমাদের জানার বিষয়, কয় জোড়া সংখ্যা গুণ করতে হয়েছে। দুই স্তূপেই ছিল পাঁচটি করে কাগজ, আর প্রথম স্তূপের পাঁচটি সংখ্যার প্রতিটিকে দ্বিতীয় স্তূপের পাঁচটি সংখ্যার প্রতিটির সঙ্গে পরীক্ষা করতে হয়েছে। মোট পরীক্ষা করেছি 5 · 5 = 25 টি জোড়া। তোমার সামনে 10 টি করে কাগজের দুইটি স্তূপ ফেললে তোমাকে 10 · 10 = 100 টি জোড়া পরীক্ষা করতে হতো। সাধারণভাবে, n টি করে কাগজের দুইটি স্তূপ ফেললে তোমাকে n · n = n2 টি জোড়া পরীক্ষা করতে হবে।

আমরা বলি, এই অ্যালগরিদমের জটিলতা n2, অর্থাৎ দ্বিঘাত জটিলতা, কারণ একে একটি দ্বিঘাত ফাংশন দিয়ে প্রকাশ করা যায়।

কিন্তু ফলাফল যাচাই করা কতটা কঠিন হবে? তুমি যদি বল যে 54 আর 17 এমন দুইটি সংখ্যা, যাদের গুণফল 918, তাহলে তোমার মতো আমাকে আর দুই স্তূপের সব জোড়া দেখতে হবে না। শুধু এই একটি জোড়া 54 · 17 গুণ করলেই আমি জানব, তুমি ঠিক বলছ কি না। অর্থাৎ এই সমস্যা সমাধান করতে n2 টি পর্যন্ত গুণফল হিসাব করতে হয়, অথচ যাচাই করতে একটিমাত্র গুণফল হিসাব করাই যথেষ্ট। তাই যাচাইয়ের জটিলতা ধ্রুবক, 1।

এখানেই আগের সমস্যার সঙ্গে এর বড় পার্থক্য। আগের সমস্যায় হিসাব করতে আর পরে যাচাই করতে একই সংখ্যক ধাপ লেগেছিল।

এই সমস্যাটি আগেরটির চেয়ে বহুগুণ কঠিনও। তোমার সামনে দশ হাজার কাগজ ঢেলে দিয়ে সবচেয়ে ছোট সংখ্যাটি খুঁজতে বললে তুমি হয়তো এক দিনেই তা খুঁজে পেতে। কিন্তু দশ হাজার করে কাগজের দুইটি স্তূপ ঢেলে দিয়ে গুণফল খুঁজতে বললে তোমাকে দশ হাজার গুণ দশ হাজার, অর্থাৎ দশ কোটি গুণফল পরীক্ষা করতে হতো। প্রতি সেকেন্ডে একটি গুণফল পরীক্ষা করলেও তোমার লাগত প্রায় তিন বছর।

সমস্যা 3: উপসেটের সমষ্টি

চল, তৃতীয় সমস্যাটি দেখি। এবার তোমার সামনে সংখ্যা লেখা বারোটি কাগজ ঢেলে দেব। আমি চাই, তুমি যতগুলো খুশি কাগজ এমনভাবে বেছে নাও, যেন তাদের যোগফল শূন্য হয়। উদাহরণ:

A={24,−69,1,−15,−76,−60,16,−83,48,−22,54,−47}

এই সংখ্যাগুলো থেকে যেকোনো একদল সংখ্যা বেছে নাও, যাদের যোগফল 0। যেমন, এই সংখ্যাগুলো

24+48−69+1

যোগ করলে পাই 4, তাই এটি সঠিক উত্তর নয়। সঠিক উত্তর হলো এই দল… নাহ্, থাক! বাড়ির কাজ হিসেবে নিজেই খুঁজে দেখ 😉। যোগফল 0 হয় এমন দল একটিই আছে। অন্তত টের পাবে, এই সমস্যা কতটা কঠিন।

এবার আমাদের এই সমস্যার জটিলতা জানা দরকার। হিসাবটি আর খুব সহজ নয়, বরং আগ্রহী পাঠকদের জন্য। তাই এই সমস্যার জটিলতা কীভাবে হিসাব করা যায়, তা জানতে চাইলে পড়তে থাক। নইলে পরের অংশে চলে যেতে পার। ⏩

তাহলে যোগফল 0 হয় এমন সংখ্যার দল কীভাবে খুঁজে পাব? সোজা কথা, সংখ্যাগুলোর সম্ভাব্য সব সমাবেশ পরীক্ষা করে দেখতে হবে। সব জোড়া, সব তিনটির দল, চারটির দল, পাঁচটির দল ইত্যাদি পরীক্ষা করতে হবে, আর প্রতিটি দলের যোগফল শূন্য কি না, তা যাচাই করতে হবে। এরকম কয়টি সমাবেশ আছে?

আরও ছোট একটি সংখ্যার সেট দিয়ে দেখি। তিনটি সংখ্যার সেট B = {5, 7, 9} থেকে সংখ্যার কয়টি ভিন্ন দল, অর্থাৎ উপসেট গঠন করা যায়? মোট আটটি:

B1={}B2={5}B3={7}B4={9}B5={5,9}B6={5,7}B7={7,9}B8={5,7,9}

লক্ষ কর, আমরা ফাঁকা উপসেট B1 কেও গুনেছি। এখন এটা খুব কাজের নয়, তবে নিয়ম রক্ষার জন্য রেখে দিয়েছি। হিসাব সহজ করতে প্রতিটি উপসেটের সঙ্গে একটি দ্বিমিক ভেক্টর (binary vector) যুক্ত করি। দ্বিমিক ভেক্টর হলো শূন্য আর একের একটি ক্রম, যেমন 00101010। আমরা কাজ করব তিন দৈর্ঘ্যের দ্বিমিক ভেক্টর নিয়ে। ভেক্টর যুক্ত করব এভাবে: 101 যুক্ত করি সেই উপসেটের সঙ্গে, যাতে আছে “প্রদত্ত সেটের প্রথম ও তৃতীয় সংখ্যা, কিন্তু দ্বিতীয় সংখ্যা নেই”, অর্থাৎ সেট {5, 9} এর সঙ্গে। ভেক্টর 110 যুক্ত করি সেই উপসেটের সঙ্গে, যাতে আছে “প্রদত্ত সেটের প্রথম ও দ্বিতীয় সংখ্যা, কিন্তু তৃতীয়টি নেই”, অর্থাৎ সেট {5, 7} এর সঙ্গে। এভাবে বাকিগুলো।

B1={}→000B2={5}→100B3={7}→010B4={9}→001B5={5,9}→101B6={5,7}→110B7={7,9}→011B8={5,7,9}→111

দেখা যাচ্ছে, প্রতিটি উপসেটের তিন দৈর্ঘ্যের দ্বিমিক ভেক্টর ঠিক একটি। আর তিন দৈর্ঘ্যের প্রতিটি দ্বিমিক ভেক্টর ঠিক একটি উপসেটের সঙ্গে মেলে। তাই n দৈর্ঘ্যের কয়টি ভিন্ন দ্বিমিক ভেক্টর আছে তা হিসাব করলে পাব, ইনপুটে n টি ভিন্ন সংখ্যা থাকলে কয়টি ভিন্ন সমাবেশ গঠন করা যায়। চল, হিসাব করি।

এক দৈর্ঘ্যের দ্বিমিক ভেক্টর দুইটি: 0 ও 1।

দুই দৈর্ঘ্যের দ্বিমিক ভেক্টর পাই এভাবে: এক দৈর্ঘ্যের সব দ্বিমিক ভেক্টর নিয়ে প্রতিটির শেষে 0 যোগ করি, পাই 00 ও 10। আবার এক দৈর্ঘ্যের সব ভেক্টর নিয়ে শেষে 1 যোগ করি: 01 ও 11। এভাবে দুই দৈর্ঘ্যের সব ভেক্টর পেলাম: 00, 01, 10 ও 11।

তিন দৈর্ঘ্যের দ্বিমিক ভেক্টর পাই এভাবে: দুই দৈর্ঘ্যের সব দ্বিমিক ভেক্টর নিয়ে শেষে শূন্য যোগ করি: 000, 010, 100 ও 110, আর এক যোগ করি: 001, 011, 101 ও 111।

পরের প্রতিটি দৈর্ঘ্যের জন্য একইভাবে চলবে। দেখা যাচ্ছে, দ্বিমিক ভেক্টরের দৈর্ঘ্য এক বাড়ালে ভিন্ন দ্বিমিক ভেক্টরের সংখ্যা দ্বিগুণ হয়। তাই চার দৈর্ঘ্যের ভেক্টরের জন্য মোট 2 · 2 · 2 · 2, অর্থাৎ 16 টি ভিন্ন সমাবেশ পাব।

সাধারণভাবে বলা যায়, সেট M এ n টি উপাদান থাকলে এই সেট M এর সব উপসেটের সংখ্যা n দৈর্ঘ্যের সব ভিন্ন দ্বিমিক ভেক্টরের সংখ্যার সমান, আর তা হলো

2⋅2⋅…⋅2⏟n−বার=2n

2n নাকি n2: একই কথা নয় কি? 🤷‍♂

তাহলে n টি সংখ্যার সেট থেকে 2n টি ভিন্ন উপসেট গঠন করা যায়। আমাদের উদাহরণে n = 12 টি সংখ্যা আছে, তাই 212 টি ভিন্ন সমাবেশ পরীক্ষা করতে হবে, অর্থাৎ 4096 টি সমাবেশ। আমরা বলি, এই সমস্যার জটিলতা 2n, অর্থাৎ সূচকীয় জটিলতা, কারণ একে একটি সূচকীয় ফাংশন দিয়ে প্রকাশ করা যায়।

লক্ষ কর, আগের সমস্যার জটিলতা ছিল n2, আর এটির 2n। দেখতে খুব কাছাকাছি, তাই না? কিন্তু সূচক ধ্রুবক হওয়া আর সূচকে চলক n থাকার মধ্যে বিরাট পার্থক্য। লক্ষ কর, n = 4 হলে পাই

n2=42=162n=24=16

বেশ, এখন পর্যন্ত দুটো একই আসছে। n = 10 হলে কী হয়?

n2=102=1002n=210=1024

আরে, সূচকীয় ফাংশন হঠাৎ লাফিয়ে উঠেছে, এটি এখন দ্বিঘাত ফাংশনের প্রায় দশ গুণ। n = 20 এর জন্য কী পাই?

n2=202=4002n=220=1 048 576

n = 20 এর জন্য সূচকীয় জটিলতার মান দ্বিঘাত জটিলতার প্রায় 2600 গুণ। তাহলে দেখা যাচ্ছে, সূচকীয় ফাংশন দ্বিঘাত ফাংশনের চেয়ে অনেক দ্রুত বাড়ে। এটা মনে রাখ, যখন আবার কোনো মহামারি সূচকীয় হারে মানুষের মধ্যে ছড়াতে থাকবে।

তাই তোমার সামনে বিশটি কাগজ ফেললে তোমাকে 10,48,576 টি সমাবেশ পরীক্ষা করতে হতো। সংখ্যাটা বেশ বড়।

ফলাফল সঠিক কি না, কীভাবে যাচাই করব?

প্রাপ্ত সংখ্যার দলের যোগফল আসলেই 0 কি না, তা যাচাই করতে আমার কত সময় লাগবে? এটা বেশ দ্রুত হবে। আমি শুধু এই একটি সংখ্যার দল যোগ করব। যোগফল 0 হলে তুমি সঠিক কাগজের দল খুঁজে পেয়েছ, অন্য কিছু হলে ভুল দল খুঁজে পেয়েছ।

আবারও দেখা যাচ্ছে, ফলাফল খুঁজে বের করার চেয়ে যাচাই করা বহুগুণ সহজ।

সমস্যা 4: ভ্রাম্যমাণ বিক্রেতার সমস্যা

ভ্রাম্যমাণ বিক্রেতার সমস্যা (travelling salesman problem) অ্যালগরিদমের সবচেয়ে বিখ্যাত সমস্যাগুলোর একটি। মোটামুটি বললে, একজন ভ্রাম্যমাণ বিক্রেতা আছেন, যিনি বৃষ্টি বিক্রি করেন। জীবিকার জন্য এই বিক্রেতাকে অনেক ঘুরতে হয়। তাই তিনি ঠিক করেছেন, বাংলাদেশের 14 টি বড় শহরের প্রতিটিতে যাবেন। আর তিনি অপচয় করতে চান না বলে এমন সবচেয়ে ছোট পথ খুঁজে বের করতে চান, যা তাঁকে এই সব শহর ঘুরিয়ে আনবে। আমাদের কাজ হলো এমন সবচেয়ে ছোট পথটি খুঁজে বের করা।

এই সবচেয়ে ছোট পথটি কীভাবে খুঁজে পাব? সব সম্ভাবনা পরীক্ষা করে।

আমরা ব্যাপারটা সরল করে নিতে পারি। ধরি, যেকোনো দুইটি শহরের মধ্যে সবচেয়ে ছোট রাস্তা একটিই। সব শহরের মধ্য দিয়ে সবচেয়ে ছোট পথ কীভাবে খুঁজে পাব? শহর আছে 14 টি। তাই কোথা থেকে শুরু করব, তার 14 টি বিকল্প। ধরা যাক, আমরা শুরু করলাম খুলনা থেকে!!! খুলনা থেকে কোথায় যাওয়া যায়? তাত্ত্বিকভাবে অন্য যেকোনো শহরে। তাই বাকি 13 টি শহর থেকে বেছে নিতে পারি।

এখনই হিসাব করা যায় যে প্রথম দুইটি শহরে যাওয়ার মোট 14 · 13 টি উপায় আছে: কোথা থেকে শুরু করব তার 14 টি বিকল্প, তারপর বাকি 13 টি শহর থেকে বেছে নেওয়া।

দ্বিতীয় শহরে পৌঁছে আমাদের আরও এগোতে হবে। দুইটি শহরে ইতিমধ্যে গেছি, তাই বাকি 12 টি শহরের যেকোনো একটিতে যেতে পারি। এভাবে প্রথম তিনটি শহরে যাওয়ার মোট 14 · 13 · 12 টি উপায় পাই।

তৃতীয় শহরে যাওয়ার পর বাকি 11 টি শহরের একটি বেছে নিতে হবে, তারপর বাকি 10 টির একটি ইত্যাদি।

সব শহরে যাওয়া শেষ হলে দেখা যাবে, আমাদের বেছে নেওয়ার মোট

14⋅13⋅12⋅11⋅10⋅9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1

টি উপায় ছিল। এটা তোমাকে ফ্যাক্টরিয়ালের কথা মনে করিয়ে দিতে পারে, যা বিস্ময়বোধক চিহ্ন দিয়ে লেখা হয়। তাই বলা যায়, এই গুণফল 14! এর সমান:

14!=14⋅13⋅12⋅11⋅10⋅9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1

অতএব এই সব শহরের মধ্য দিয়ে যাওয়া পথ আছে 14! টি। এটা কি অনেক? বেশ অনেক, কারণ

14!=87 178 291 200.

সাধারণভাবে, n টি শহরের মধ্যে সবচেয়ে ছোট পথ খুঁজতে হলে n! টি ভিন্ন পথ পরীক্ষা করতে হতো। তাই এই সমাধানের জটিলতা n!।

সঠিক ফলাফল পেয়েছি কি না, তা কীভাবে যাচাই করব? তুমি যদি বল যে সবচেয়ে ছোট পথ হলো সিলেট থেকে খুলনা, তারপর চট্টগ্রাম ইত্যাদি, তাহলে তুমি সত্যি বলছ কি না, তা আমি কীভাবে যাচাই করব? সেটা বেশ কঠিন 🤷‍♂। কারণ পথটি দেখে এটাই সবচেয়ে ছোট পথ কি না, তা সহজে যাচাই করার কোনো উপায় আমার নেই। আসলে পুরো হিসাবটাই আমাকে আবার করতে হবে। তাই ফলাফল যাচাইয়ের জটিলতাও n!।

P ও NP শ্রেণি

আমরা চারটি সমস্যা আর এদের সমাধানের অ্যালগরিদম দেখলাম। বিশ্লেষণ করলাম, সমাধান খুঁজে বের করা কতটা কঠিন আর সেই সমাধান যাচাই করা কতটা কঠিন। সব কিছু এই সারণিতে সংক্ষেপে দেওয়া হলো:

সমস্যা সমাধানের জটিলতা যাচাইয়ের জটিলতা
সবচেয়ে ছোট সংখ্যা n n
জোড়ার গুণফল n2 1
উপসেটের সমষ্টি 2n n
ভ্রাম্যমাণ বিক্রেতা n! n!

এবার আমাদের সমস্যাগুলোকে দুইটি দলে ভাগ করি। প্রথম দলে থাকবে সেসব সমস্যা, যেগুলো সমাধান করা সহজ। এগুলো এমন সমস্যা, যা n বা n2 বা n3 বা n4 ইত্যাদি জটিলতায় সমাধান করা যায়। n2 এর মতো রাশিকে আমরা বহুপদী (polynomial) বলি, তাই সমস্যার এই শ্রেণিকে P অক্ষর দিয়ে চিহ্নিত করা হয়। অর্থাৎ P শ্রেণিতে আছে সেসব সমস্যা, যা বহুপদী সময়ে সমাধান করা যায় (জটিলতা যেমন n2 বা n7)। সাধারণভাবে, এগুলো এমন সমস্যা, যা মোটামুটি সহজে সমাধান করা যায়।

তাই P শ্রেণিতে পড়ে সমস্যা 1, অর্থাৎ সবচেয়ে ছোট সংখ্যা খোঁজা, কারণ এর সমাধানের জটিলতা n। আর পড়ে সমস্যা 2, অর্থাৎ জোড়ার গুণফল, কারণ এর সমাধানের জটিলতা n2। দুটোই বহুপদী।

দ্বিতীয় শ্রেণি হলো NP শ্রেণি। এতে আছে সেসব সমস্যা, যাদের সমাধান বহুপদী সময়ে যাচাই করা যায়। তাই শেষটি ছাড়া সব সমস্যাই NP শ্রেণিতে পড়ে। ভ্রাম্যমাণ বিক্রেতার সমস্যার সমাধান বহুপদী সময়ে যাচাই করার কোনো উপায় আমাদের জানা নেই। আগের তিনটি সমস্যা বহুপদী সময়ে যাচাই করা যায়।

ভ্রাম্যমাণ বিক্রেতার সমস্যা আমরা বহুপদী সময়ে সমাধানও করতে পারি না, যাচাইও করতে পারি না। তাই এর জন্য আরেকটি শ্রেণি দরকার, যাতে থাকবে আরও কঠিন সমস্যা। এমন শ্রেণি আছে, কিন্তু এই মুহূর্তে তা আমাদের আলোচনার বিষয় নয়।

স্পষ্টতই P শ্রেণি NP শ্রেণির উপসেট। অর্থাৎ P শ্রেণির প্রতিটি সমস্যা NP শ্রেণিতেও আছে। এটা যুক্তিসংগত: কোনো সমস্যা বহুপদী সময়ে সমাধান করতে পারলে তার ফলাফলও বহুপদী সময়ে যাচাই করতে পারব।

P বনাম NP সমস্যা

উল্টোটাও কি সত্য? NP শ্রেণির প্রতিটি সমস্যা কি P শ্রেণিতেও আছে? অর্থাৎ কোনো সমস্যার ফলাফল বহুপদী সময়ে যাচাই করার উপায় থাকলে এমন কোনো অ্যালগরিদমও কি আছে, যা সমস্যাটি বহুপদী সময়ে সমাধান করবে?

উদাহরণ হিসেবে, আমরা জানি যে সমস্যা 3, অর্থাৎ উপসেটের সমষ্টির ফলাফল বহুপদী সময়ে যাচাই করা যায়। কিন্তু এর সমাধানে আমরা যে অ্যালগরিদম ব্যবহার করেছি, তা বহুপদী নয়, তার জটিলতা সূচকীয়, 2n। কিন্তু আমরা কি নিশ্চিতভাবে জানি যে এই সমস্যার জন্য বহুপদী জটিলতার কোনো অ্যালগরিদম নেই?

জানি না!

এমনও হতে পারে যে বহুপদী সময়ে যাচাই করা যায় এমন প্রতিটি সমস্যার জন্য এমন একটি অ্যালগরিদম আছে, যা সমস্যাটি বহুপদী সময়ে সমাধান করে। আমরা তা জানি না। এমন অ্যালগরিদমের অস্তিত্ব আমরা প্রমাণ করতে পারি না, আবার এর অস্তিত্ব খণ্ডনও করতে পারি না।

NP শ্রেণির প্রতিটি সমস্যার জন্য যদি বহুপদী সময়ে সমাধান করার অ্যালগরিদম থাকত, তার মানে হতো NP শ্রেণি আসলে P শ্রেণির সমান। P শ্রেণির সব সমস্যা থাকত NP শ্রেণিতে, আর NP শ্রেণির সব সমস্যা থাকত P শ্রেণিতে। দুই শ্রেণি সমান হতো, অভিন্ন হতো।

তাহলে P বনাম NP সমস্যা হলো এই প্রশ্ন: P শ্রেণি কি NP শ্রেণির সঙ্গে অভিন্ন, নাকি এরা সমস্যার দুইটি ভিন্ন শ্রেণি?

অর্থাৎ হয় P = NP, নয়তো P ≠ NP। এটা কেউ জানে না। তুমি যদি এর উত্তর বের করতে পার, তাহলে তোমার জন্য অপেক্ষা করছে দশ লাখ ডলার পুরস্কার, অমর খ্যাতি, আর সম্ভবত টুরিং পুরস্কারও, যা কম্পিউটার বিজ্ঞানীদের জন্য এক রকম নোবেল পুরস্কার।

P = NP হলে কী হতো?

P = NP সত্য হলে কী হতো? কী হতো তা বলা খুব সহজ নয়। আমরা জানতাম, NP শ্রেণির সব সমস্যার জন্য এমন অ্যালগরিদম আছে, যা এদের বহুপদী সময়ে সমাধান করে। যেমন, আমাদের সমস্যা 3, অর্থাৎ উপসেটের সমষ্টির জন্য বহুপদী সময়ে সমাধান করার অ্যালগরিদম আছে। কিন্তু এতে তিনটি প্যাঁচ আছে:

  • এমন অ্যালগরিদম আছে বলে জানলেই যে আমরা তা খুঁজে পাব, তা নয়। আমরা শুধু জানতাম যে হ্যাঁ, বহুপদী সময়ে সমস্যাটি সমাধান করার অ্যালগরিদম আছে, কিন্তু হয়তো আরও একশ বছরেও তা তৈরি করতে পারতাম না। ব্যাপারটা অনেকটা এরকম: সাধারণ আপেক্ষিকতা তত্ত্ব কৃষ্ণগহ্বরের অস্তিত্বের পূর্বাভাস দিয়েছিল, তবু কৃষ্ণগহ্বরের প্রথম “ছবি” তুলতে আমাদের আরও কয়েক দশক লেগে গেছে।
  • বহুপদী সময়ে কাজ করে এমন অ্যালগরিদম থাকলেই দুর্ভাগ্যবশত তা দ্রুত হবে, এমন নয়। আমরা এমন অ্যালগরিদম পেতে পারি, যার জটিলতা n100। কারণ n100 রাশিটিও একটি বহুপদী। 2n আর n100 জটিলতার তুলনা করলে দেখা যায়, n তুলনামূলক ছোট থাকা পর্যন্ত 2n জটিলতার অ্যালগরিদমেই কম প্রক্রিয়া লাগে। যেমন, n = 20 এর জন্য 220 = 10,48,576, অথচ 20100 রাশিটি থেকে প্রায় 130 অঙ্কের একটি সংখ্যা পাওয়া যায়। এই সংখ্যা 10,48,576 এর চেয়ে প্রায় দশের 120 তম ঘাত গুণ বড়। তাই বাস্তবে আমাদের বহুপদী অ্যালগরিদম সূচকীয়টির চেয়ে ধীর হতো। অন্তত যতক্ষণ n তুলনামূলক ছোট।
  • যদি আমরা সত্যিই বহুপদী সময়ে কাজ করে এমন দ্রুত অ্যালগরিদম খুঁজে পেতাম, তাহলে অনেক সমস্যা আরও দ্রুত ও আরও নির্ভুলভাবে সমাধান করতে পারতাম। এটা অবশ্যই সুখবর, কিন্তু এর খারাপ দিকও আছে। একটি শাস্ত্র এই ভরসায় চলে যে কিছু সমস্যা সমাধান করা কঠিন, সেটি হলো ক্রিপ্টোগ্রাফি, অর্থাৎ এনক্রিপশন। ফলে বর্তমান সাইফারগুলো ভাঙা বহুগুণ সহজ হয়ে যেতে পারত।

বিরতি: তুমি এতদূর পড়েছ, তাই পুরস্কার হিসেবে বলে দিচ্ছি, সমস্যা 3 এর সমাধান হলো 24 + 1 − 60 + 16 − 83 + 48 + 54।

P ≠ NP হলে কী হতো?

যদি সত্য হতো যে P ও NP সমস্যার দুইটি ভিন্ন শ্রেণি, তাহলে তেমন কিছুই ঘটত না, কারণ বর্তমান অবস্থা মোটামুটি এটাই। NP শ্রেণির কোনো কঠিন সমস্যা বহুপদী সময়ে সমাধান করে এমন কোনো অ্যালগরিদম এখন আমাদের হাতে নেই। কেউ যদি প্রমাণ করত যে P ≠ NP, তাহলে অবস্থা চিরকাল এরকমই থাকত। এর চেয়ে অনেক বড় চমক হতো P = NP এর প্রমাণ।

জনপ্রিয় সংস্কৃতিতে উল্লেখ

  • দ্য সিম্পসনস (The Simpsons) কার্টুনের একটি পর্বে দেখা যায়, হোমার এক ধরনের বিকল্প বাস্তবতায় পৌঁছে যায়, যেখানে তার সামনে প্রকাশ পায় যে P = NP। দেখতে পার youtube.com এ।
  • আবার ফিউচুরামা (Futurama) কার্টুনে দেখা যায়, গুদামে দুইটি ফোল্ডার আছে, একটির নাম P আর অন্যটির নাম NP। দেখতে পার youtube.com এ।
  • এলিমেন্টারি (Elementary) ধারাবাহিকের দ্বিতীয় সিজনের দ্বিতীয় পর্ব “Solve for X” এ এমন এক গণিতবিদের হত্যার ঘটনা দেখানো হয়েছে, যিনি সম্ভবত P বনাম NP সমস্যার সমাধান করে ফেলেছিলেন।