فراز تیرے جنوں کا خیال ہے ورنہ عدنان مسعود کی سخن آرایاں۔ دروغ برگردن قاری

پی اور این پی بتانے سے پہلے پہلے ایک چھوٹی سی تمہید باندھتے ہیں۔آپ نے وہ کہانی تو ضرور سنی ہوگی کہ ایک بادشاہ نے ایک درباری سے خوش ہوکر کہا مانگ کیا مانگتا ہے۔ وہ درباری بادشاہ کی شومئی قسمت سے ریاضی دان تھا جس نےمسکراتے ہوئے فرمائش کی کہ شطرنج کے پہلے خانے میں ایک اشرفی رکھی جائے پھر دوسرے میں دو  پھر دوسرے خانے میں موجود تعداد کو اسی تعداد سے ضرب دیا جائے ( یعنی ۲ ضرب ۲ =4) اور جواب تعداد ( 4) کو تیسرے خانے میں رکھا جائے پھر چوتھے خانے میں بھی یہی عمل دہرایا جائے ( یعنی ۴ضرب ۴ =16 ) اس حاصل ضرب تعداد کے برابر اشرفیوں کوچوتھے خانے میں رکھا جائےاسی طرح یہ عمل ہر خانے میں دہراتے ہوئے کل چونسٹھ خانے میں اشرفیاں رکھی جائيں اور وہ تمام اشرفیاں مجھے انعام میں دے دیا جائے۔
پہلے تو بادشاہ اس عجیب فرمائشی انعام پر ہنسا کہ اتنی سی مقدار میں خزانہ مانگ رہا ہے تو اس نے اپنے خزانچی کو حکم دیا کہ جس حساب سے یہ اشرفیاں مانگ رہا ہے اسے دے دیا جائے۔ خزانچی حساب لگانے اور اشرفیاں دینے کے لئے گیا مگر پھر واپس دوڑا ہوا آیا اور ڈرتے ڈرتے بتایا کہ اسی طریقے سے جو اشرفیوں کی مقدار بنتی ہے وہ تو ہمارے خزانےیا سلطنت میں تو دور کی بات پوری دنیا میں شائد اتنا سونا نا ہو کے اتنی اشرفیاں بنائی جا سکیں۔

اسے کامبنیٹرل ایکپلوژن کہا جاتا ہے اور یہ بولین سیٹسفایبلٹی پرابلم کی اساس ہے۔ پی اور این پی مسائل کا مطالعہ ایک نہائت مزیدار مضمون اور پی بمقابل این پی کمپیوٹر سائنیس کاایک نہایت دقیق غیر حل شدہ مسئلہ ہے جس کے حل پر ایک ملین ڈالر کا انعام رکھا گیا ہے۔ اس کو ایک اور کامبینیٹرل ایکپلوژن مثال سے اس طرح بتایا جاسکتا ہے کہ آپ جامعہ کراچی میں انڈر گریجویٹ طالب علموں کے سربراہ  ہیں اور آپ نے 1،000 طالب علموں کو  10 ڈپارٹمنٹوں یا شعبہ جات میں‌ داخلہ دینا ہے۔ ہر طالب علم ایک فہرست پیش کرتا ہے کہ وہ کن دیگر طالبعلموں کے ساتھ پڑھنا پسند یا ناپسند کرتا ہے۔ اس سادے سے مسئلے میں کیا آپ سمجھتے ہیں کہ آپ کے طالب علموں کی ترجیحات کو مطمئن کر سکتے ہیں اور کیا  کمپیوٹنگ کا استعمال کرتے ہوئے اس مسئلے کو  حل کیا جا سکتا ہے؟

عام سا لگنے والا یہ مسئلہ اتنا آسان نہیں۔  طالب علموں کے ممکنہ کامبینیشیز کی تعداد ایک نہایت ہی بڑا عدد بن جاتی ہے۔ یہ عدد ہے ایک کے بعد ایک ہزار صفر! یہ تعداد شاید کائنات میں بنیادی ذرات کی تعداد سے بھی ذیادہ ہے اس طرح اندازہ لگایئے کہ اگر ہم ایک ٹرلین کامبنیشنز یا تفاویض کوایک سیکنڈ میں چیک کرتے ہیں پھر بھی تمام اسائنمنٹس دیکھنے میں ٹریلین ، ٹریلین،  ٹریلین  سال لگ جائیں گے۔ اس طرح کی تلاش کو  جامع تلاش کہا جاتا ہے اور یہ کمپیوٹیشنلی بہت مہنگا پڑتا ہے!

 کسی بھی کمپیوٹر الگارتھم کی ایک اہم خصوصیت اس کی کمپلیکسٹی یا پیچیدگی کا پیمانا ہوتا ہے۔ اس پیمانے کو لینیر یا خطی، کواڈریٹک، لاگ، پولینومیل یا متعدد الحدود اور ایکسپونینشیل یا قوت نما کے پیمانوں سے ناپا جاتا ہے۔اس زمن میں اس بات کا خیال رکھنا بھی ضروری ہوتا ہے کہ یہ الگارتھم جگہ اور وقت دونوں کے لئے بہتر طریقے سے اصلاح شدہ ہو۔  یعنی کوئی الگارتھم زیادہ میموری استعمال کر کر جلدی جواب لا دے تو اسکا استعمال چھوٹے ڈوایسز میں جن میں‌ میموری کی کمی ہوتی ہے آسانی سے نہیں ہوسکتا۔ یہی حال پراسسنگ پاور کا ہے کہ اگر ایک الگارتھم کم جگہ لیتا ہو لیکن جواب لانے کے لئے ٹیرا فلاپس میں ہدایات کو چلانا مقصود ہو تو اسکا استعمال بھی محدود ہو جاتا ہے۔ مثال کے طور پر کسی پرائم نمبر کے حل کی تصدیق تو نہایت آسان کام ہے لیکن اسے ڈھونڈنے کے لئے اس کو لاکھوں کروڑوں اعداد سے تقسیم کرنا ایک بروٹ فورس مرحلہ ہے جو ہر بڑھنے والے پرائم کے ساتھ مشکل ہوتا چلا جاتا ہے۔

پی مسائل ایسےہوتے ہیں جن کا پولینومیل ٹائم میں جواب ڈھونڈا جاسکتا ہے اور اس جواب کی تصدیق کی جاسکتی ہے۔ پولینومیل ٹایم سے عام الفاظ میں مراد اتنا وقت ہے جس کا اوپری باونڈ پولینومیل کلئے سے ظاہر کیا جا سکتا ہو۔  این پی یا ‘نان ڈٹرمنسٹک پولینومیل ٹایم’ مسئلے سے مراد ایسا مسئلہ  ہے جو کہ حل ہونے میں بہت وقت لیتا ہو اور اس کے حل کی تصدیق پولینومیل وقت میں ہوسکتی ہو۔ حل کی تصدیق درحقیقت یہاں تعریف کی اصل حقیقت ہے۔ این پی مسائل ناممکن نہیں ہوتے، صرف بہت مشکل ہوتے ہیں۔ ان کی فہرست یہاں دیکھی جا سکتی ہے۔

اکثر محققین کی حس مزاح کو گدگدانے والا  ملین ڈالر کا سوال یہ ہے کہ کیا پی اور این پی برابر ہیں-یعنی کہ اگر کس مسئلے کی پولینومیل وقت میں تصدیق کی جاسکتی ہے تو کیا مستقبل میں انسانی علم اس قابل ہوسکتا ہے کہ اس مسئلے کو پولینومیل وقت میں حل بھی کیا جاسکے۔ اگر ہاں‌ تو اسکا حسابی ثبوت کیا ہے؟ یہ مسئلہ ساینسی اذہان کو پواینکیر کنچیکچر اور فرماٹ کے آخری تھیورم کے بعد سب سے ذیادہ مصروف رکھنے والا معمہ ہے۔ محققین کی ایک چھوٹی سی راے شماری کے مطابق ایک بڑی تعداد سمجھتی ہے کہ پی اور این پی برابر نہیں۔ میرا خیال اسکے برعکس ہے لیکن ڈانلڈ نتھ کی طرح میری راے بھی اقلیتی ہے۔ 🙂