Cobham's thesis
کوبھم کا مقالہ، جسے کوبھم ایڈمنڈز تھیسس (ایلن کوبھم اور جیک ایڈمنڈز کے نام سے بھی جانا جاتا ہے)، اس بات پر زور دیتا ہے کہ کمپیوٹیشنل مسائل کو کسی کمپیوٹیشنل ڈیوائس پر تب ہی قابل عمل طریقے سے شمار کیا جا سکتا ہے جب ان کا حساب کثیر الجہتی وقت میں کیا جا سکے۔ یعنی، اگر وہ پیچیدگی کی کلاس P میں ہوں۔ جدید اصطلاحات میں، یہ پیچیدگی کی کلاس P کے ساتھ قابل حل مسائل کی نشاندہی کرتا ہے۔ رسمی طور پر، یہ کہنا کہ کسی مسئلے کو کثیر الجہتی وقت میں حل کیا جا سکتا ہے، یہ کہنا ہے کہ ایک الگورتھم موجود ہے، جس میں مسئلے کی n-بٹ مثال کو ان پٹ کے طور پر دیا گیا ہے، بگ-O نوٹیشن کا استعمال کرتے ہوئے وقت O (nc) میں حل پیدا کر سکتا ہے اور c ایک مستقل ہونے کے ساتھ جو مسئلے پر منحصر ہے لیکن مسئلہ پر نہیں۔ ایلن کوبھم کا 1965 کا مقالہ جس کا عنوان ہے "افعال کی اندرونی کمپیوٹیشنل مشکل" پیچیدگی کلاس P کے تصور کے ابتدائی ذکر میں سے ایک ہے، جو کثیر الجہتی وقت میں فیصلہ کن مسائل پر مشتمل ہے۔ کوبھم نے نظریہ پیش کیا کہ یہ پیچیدگی کلاس ممکنہ طور پر کمپیوٹیبل مسائل کے سیٹ کو بیان کرنے کا ایک اچھا طریقہ ہے۔ جیک ایڈمنڈز کے 1965 کے مقالے "پاتھز، ٹریز، اینڈ فلاورز" کو بھی قابل علاج مسائل کے ساتھ پی کی شناخت کرنے کا سہرا دیا جاتا ہے۔ حدود اگرچہ کوبھم کا مقالہ کمپیوٹیشنل پیچیدگی کے نظریہ کی ترقی میں ایک اہم سنگ میل ہے، لیکن اس کی حدود ہیں جو الگورتھم کی عملی فزیبلٹی پر لاگو ہوتی ہیں۔ مقالہ بنیادی طور پر کہتا ہے کہ "پی" کا مطلب "آسان، تیز اور عملی" ہے، جبکہ "پی میں نہیں" کا مطلب "سخت، سست اور ناقابل عمل" ہے۔ لیکن یہ ہمیشہ درست نہیں ہوتا، کیونکہ مقالہ کچھ اہم متغیرات کو خلاصہ کرتا ہے جو عملی طور پر رن ٹائم کو متاثر کرتے ہیں: یہ مستقل عوامل اور نچلے درجے کی شرائط کو نظر انداز کرتا ہے۔ یہ ایکسپوینٹ کے سائز کو نظر انداز کرتا ہے۔ وقت کی درجہ بندی کا نظریہ P میں مسائل کے وجود کو ثابت کرتا ہے جس میں من مانی طور پر بڑے متغیرات کی ضرورت ہوتی ہے۔ یہ ان پٹ کے عام سائز کو نظر انداز کرتا ہے۔ تینوں ایک دوسرے سے متعلق ہیں اور الگورتھم کے تجزیے کے بارے میں عمومی شکایات ہیں، لیکن وہ خاص طور پر کوبھم کے مقالے پر لاگو ہوتے ہیں، کیونکہ یہ عملیت کے بارے میں واضح دعوی کرتا ہے۔ کوبھم کے مقالے کے تحت، ایک مسئلہ جس کے لیے بہترین الگورتھم n200 ہدایات لیتا ہے اسے قابل عمل سمجھا جاتا ہے، اور ایک الگورتھم کے ساتھ ایک مسئلہ جو 20.00001 n ہدایات کو ناقابل عمل بناتا ہے-حالانکہ کوئی بھی سائز n = 2 کی مثال کو سابقہ الگورتھم کے ساتھ کبھی حل نہیں کر سکتا تھا، جبکہ سائز n = 106 کے مؤخر الذکر مسئلے کی مثال کو بغیر کسی مشکل کے حل کیا جا سکتا تھا۔ ایسے شعبوں میں جہاں عملی مسائل میں لاکھوں متغیرات ہوتے ہیں (جیسے کہ آپریشنز ریسرچ یا الیکٹرانک ڈیزائن آٹومیشن)، یہاں تک کہ O (n3) الگورتھم اکثر ناقابل عمل ہوتے ہیں۔ ایک علیحدہ غور یہ ہے کہ بہت سے معاملات میں، اگر کوئی صحیح حل نہیں مل پاتا ہے تو اکثر قریب قریب حل کے ساتھ مطمئن ہوتا ہے۔ مثال کے طور پر، ٹریول سیلز مین کا مسئلہ کثیر الجہتی وقت میں بالکل حل نہ ہونے کا وسیع پیمانے پر شبہ ہے (یہ این پی-ہارڈ ہے)، لیکن کرسٹوفائڈز الگورتھم جیسے طریقوں سے کثیر الجہتی وقت میں اچھے حل حاصل کیے جا سکتے ہیں۔ حوالہ جات کمپیوٹیشنل پیچیدگی کا نظریہ