EITC/IS/CCTF Computational Complexity Theory Fundamentals ایک یورپی IT سرٹیفیکیشن پروگرام ہے جو کمپیوٹر سائنس کی بنیادوں کے نظریاتی پہلوؤں پر ہے جو کہ انٹرنیٹ میں وسیع پیمانے پر استعمال ہونے والی کلاسیکی غیر متناسب عوامی کلیدی خفیہ نگاری کی بنیاد بھی ہے۔
EITC/IS/CCTF کمپیوٹیشنل کمپلیکسٹی تھیوری بنیادی اصولوں کا نصاب کمپیوٹر سائنس کی بنیادوں پر نظریاتی علم اور کمپیوٹیشنل ماڈلز پر بنیادی تصورات جیسے deterministic اور nondeterministic finite state machines، باقاعدہ زبانیں، سیاق و سباق سے پاک گرامر اور لینگویج تھیوری، آٹومیٹا تھیوری، ٹورنگ کا احاطہ کرتا ہے۔ مندرجہ ذیل ڈھانچے کے اندر بنیادی حفاظتی ایپلی کیشنز کے لیے مشینیں، مسائل کا فیصلہ کرنے کی صلاحیت، تکرار، منطق اور الگورتھمکس کی پیچیدگی، اس EITC سرٹیفیکیشن کے حوالے کے طور پر جامع ویڈیو ڈیڈیکٹک مواد کو شامل کرتا ہے۔
ایک الگورتھم کی کمپیوٹیشنل پیچیدگی اس کو چلانے کے لیے درکار وسائل کی مقدار ہے۔ وقت اور یادداشت کے وسائل پر خصوصی توجہ دی جاتی ہے۔ کسی مسئلے کی پیچیدگی کو حل کرنے کے لیے بہترین الگورتھم کی پیچیدگی سے تعبیر کیا جاتا ہے۔ الگورتھم کا تجزیہ واضح طور پر دیے گئے الگورتھم کی پیچیدگی کا مطالعہ ہے، جبکہ کمپیوٹیشنل پیچیدگی نظریہ بہترین معلوم الگورتھم کے ساتھ مسائل کے حل کی پیچیدگی کا مطالعہ ہے۔ دونوں ڈومین ایک دوسرے سے جڑے ہوئے ہیں کیونکہ الگورتھم کی پیچیدگی ہمیشہ اس مسئلے کی پیچیدگی پر ایک اوپری رکاوٹ ہوتی ہے جسے وہ حل کرتا ہے۔ مزید برآں، یہ اکثر ضروری ہوتا ہے کہ ایک مخصوص الگورتھم کی پیچیدگی کا موازنہ اس مسئلے کی پیچیدگی سے کیا جائے جس کو موثر الگورتھم بناتے ہوئے حل کیا جائے۔ زیادہ تر حالات میں، کسی مسئلے کی دشواری کے بارے میں دستیاب واحد معلومات یہ ہے کہ یہ سب سے زیادہ موثر معلوم تکنیکوں کی پیچیدگی سے کم ہے۔ نتیجے کے طور پر، الگورتھم کے تجزیہ اور پیچیدگی کے نظریہ کے درمیان بہت زیادہ اوورلیپ ہے۔
کمپلیکسیٹی تھیوری نہ صرف کمپیوٹر سائنس کی بنیاد کے طور پر کمپیوٹیشنل ماڈلز کی بنیادوں میں اہم کردار ادا کرتی ہے بلکہ کلاسیکی غیر متناسب کرپٹوگرافی کی بنیادوں میں بھی اہم کردار ادا کرتی ہے جو کہ جدید نیٹ ورکس، خاص طور پر انٹرنیٹ میں وسیع پیمانے پر پھیلی ہوئی ہے۔ عوامی کلید کی خفیہ کاری بعض غیر متناسب ریاضیاتی مسائل کے کمپیوٹیشنل مشکل پر مبنی ہے جیسے کہ بڑی تعداد کو اس کے بنیادی عوامل میں فیکٹرائزیشن (یہ آپریشن پیچیدگی نظریہ کی درجہ بندی میں ایک مشکل مسئلہ ہے، کیونکہ حل کرنے کے لیے معلوم موثر کلاسیکی الگورتھم نہیں ہیں۔ یہ مسئلے کے ان پٹ سائز میں اضافے کے ساتھ کثیر نامی طور پر وسائل کے ساتھ اسکیلنگ کرتا ہے، جو کہ اصل بڑی تعداد دینے کے لیے معلوم پرائم فیکٹرز کو ضرب دینے کے ایک بہت ہی آسان ریورس آپریشن کے برعکس ہے)۔ عوامی کلید کی کرپٹوگرافی کے فن تعمیر میں اس توازن کو استعمال کرتے ہوئے (عوامی کلید کے درمیان ایک کمپیوٹیشنل غیر متناسب تعلق کی وضاحت کرتے ہوئے، جو آسانی سے ایک نجی کلید سے شمار کیا جا سکتا ہے، جب کہ نجی کلید کو عوامی کلید سے آسانی سے کمپیوٹر نہیں بنایا جا سکتا، کوئی عوامی کلید کے درمیان آسانی سے شمار کیا جا سکتا ہے۔ عوامی کلید کا اعلان کریں اور دیگر مواصلاتی فریقوں کو ڈیٹا کی غیر متناسب خفیہ کاری کے لیے اسے استعمال کرنے کے قابل بنائیں، جسے صرف مشترکہ نجی کلید کے ساتھ ہی ڈکرپٹ کیا جا سکتا ہے، جو کہ تیسرے فریق کے لیے کمپیوٹیشنل طور پر دستیاب نہیں ہے، اس طرح مواصلات کو محفوظ بنایا جائے گا)۔
کمپیوٹیشنل پیچیدگی کا نظریہ بنیادی طور پر کمپیوٹر سائنس اور الگورتھم کے علمبرداروں کی کامیابیوں پر تیار کیا گیا تھا، جیسے کہ ایلن ٹیورنگ، جن کا کام نازی جرمنی کے اینگما سائفر کو توڑنے کے لیے اہم تھا، جس نے دوسری عالمی جنگ جیتنے والے اتحادیوں میں گہرا کردار ادا کیا۔ خفیہ تجزیے کا مقصد ڈیٹا کا تجزیہ کرنے کے کمپیوٹیشنل عمل (بنیادی طور پر انکرپٹڈ کمیونیکیشن) کو وضع کرنا اور خودکار بنانا ہے تاکہ پوشیدہ معلومات کو بے نقاب کیا جا سکے اور خفیہ معلومات کے نظام کی خلاف ورزی کرنے اور انکرپٹڈ کمیونیکیشن کے مواد تک رسائی حاصل کرنے کے لیے استعمال کیا جاتا ہے، عام طور پر اسٹریٹجک فوجی اہمیت کے۔ یہ خفیہ تجزیہ بھی تھا جس نے پہلے جدید کمپیوٹرز کی ترقی کو متحرک کیا (جو ابتدائی طور پر کوڈ بریکنگ کے اسٹریٹجک مقصد پر لاگو کیا گیا تھا)۔ برٹش کولوسس (پہلے جدید الیکٹرانک اور پروگرام کمپیوٹر کے طور پر سمجھا جاتا ہے) سے پہلے پولش "بم" تھا، ایک الیکٹرانک کمپیوٹیشنل ڈیوائس جسے ماریان ریجیوسکی نے اینیگما سائفرز کو توڑنے میں مدد کے لیے ڈیزائن کیا تھا، اور اسے پولش انٹیلی جنس نے برطانیہ کے حوالے کیا تھا۔ 1939 میں جرمنی کی طرف سے پولینڈ پر حملہ کرنے کے بعد پکڑی گئی جرمن اینیگما انکرپشن مشین۔ اس ڈیوائس کی بنیاد پر ایلن ٹورنگ نے جرمن انکرپٹڈ کمیونیکیشن کو کامیابی کے ساتھ توڑنے کے لیے اپنا مزید جدید ہم منصب تیار کیا، جسے بعد میں جدید کمپیوٹرز میں تیار کیا گیا۔
چونکہ الگورتھم کو چلانے کے لیے درکار وسائل کی مقدار ان پٹ کے سائز کے ساتھ مختلف ہوتی ہے، اس لیے پیچیدگی کو عام طور پر ایک فنکشن f(n) کے طور پر ظاہر کیا جاتا ہے، جہاں n ان پٹ کا سائز ہے اور f(n) یا تو بدترین کیس کی پیچیدگی ہے ( سائز n کے تمام ان پٹس میں درکار وسائل کی زیادہ سے زیادہ مقدار) یا اوسط کیس کی پیچیدگی (سائز n کے تمام ان پٹ پر وسائل کی مقدار کی اوسط)۔ سائز n کے ان پٹ پر مطلوبہ ابتدائی کارروائیوں کی تعداد کو عام طور پر وقت کی پیچیدگی کے طور پر بیان کیا جاتا ہے، جہاں یہ خیال کیا جاتا ہے کہ ابتدائی کارروائیوں کو کسی خاص کمپیوٹر پر مستقل وقت لگتا ہے اور جب کسی مختلف مشین پر چلایا جاتا ہے تو صرف ایک مستقل عنصر سے تبدیل ہوتا ہے۔ سائز n کے ان پٹ پر الگورتھم کے لیے درکار میموری کی مقدار کو خلائی پیچیدگی کے نام سے جانا جاتا ہے۔
وقت عام طور پر سمجھا جانے والا وسیلہ ہے۔ جب اصطلاح "پیچیدگی" کوالیفائر کے بغیر استعمال کی جاتی ہے، تو یہ عام طور پر وقت کی پیچیدگی سے مراد ہے۔
وقت کی روایتی اکائیاں (سیکنڈ، منٹ، اور اسی طرح) کو پیچیدگی تھیوری میں استعمال نہیں کیا جاتا ہے کیونکہ وہ کمپیوٹر کے منتخب کردہ اور ٹیکنالوجی کی ترقی پر بہت زیادہ انحصار کرتے ہیں۔ مثال کے طور پر، آج ایک کمپیوٹر 1960 کی دہائی کے کمپیوٹر سے کافی تیزی سے الگورتھم کو چلا سکتا ہے، پھر بھی، یہ الگورتھم کے موروثی معیار کی بجائے کمپیوٹر ہارڈویئر میں تکنیکی کامیابیوں کی وجہ سے ہے۔ پیچیدگی کے نظریہ کا مقصد الگورتھم کی موروثی وقت کی ضروریات، یا ان بنیادی وقت کی حدود کو درست کرنا ہے جو الگورتھم کسی بھی کمپیوٹر پر عائد کرے گا۔ یہ شمار کرکے پورا کیا جاتا ہے کہ حساب کے دوران کتنے بنیادی آپریشن کیے جاتے ہیں۔ ان طریقہ کار کو عام طور پر اقدامات کے طور پر کہا جاتا ہے کیونکہ یہ ایک خاص مشین پر مستقل وقت لینے کے لئے سمجھا جاتا ہے (یعنی، وہ ان پٹ کی مقدار سے متاثر نہیں ہوتے ہیں)۔
ایک اور اہم وسیلہ الگورتھم کو انجام دینے کے لیے درکار کمپیوٹر میموری کی مقدار ہے۔
ایک اور اکثر استعمال ہونے والا وسیلہ ریاضی کی کارروائیوں کی مقدار ہے۔ اس منظر نامے میں، "ریاضی کی پیچیدگی" کی اصطلاح استعمال ہوتی ہے۔ وقت کی پیچیدگی عام طور پر ایک مستقل عنصر کے ذریعہ ریاضی کی پیچیدگی کی پیداوار ہوتی ہے اگر حساب کے دوران ہونے والے اعداد کی بائنری نمائندگی کے سائز پر اوپری رکاوٹ معلوم ہو۔
حساب کے دوران استعمال شدہ عدد کا سائز بہت سے طریقوں کے لیے محدود نہیں ہے، اور یہ فرض کرنا غیر حقیقی ہے کہ ریاضی کی کارروائیوں کو ایک مقررہ وقت کی ضرورت ہوتی ہے۔ نتیجے کے طور پر، وقت کی پیچیدگی، جسے بٹ پیچیدگی بھی کہا جاتا ہے، ریاضی کی پیچیدگی سے نمایاں طور پر زیادہ ہو سکتی ہے۔ nn انٹیجر میٹرکس کا تعین کرنے میں ریاضی کی دشواری، مثال کے طور پر، معیاری تکنیکوں کے لیے O(n^3) ہے (گاؤس کے خاتمے)۔ چونکہ گتانک کا سائز حساب کے دوران تیزی سے پھیل سکتا ہے، اسی طریقوں کی تھوڑی پیچیدگی n میں ایکسپونینشل ہے۔ اگر ان تکنیکوں کو ملٹی ماڈیولر ریاضی کے ساتھ استعمال کیا جائے تو بٹ کی پیچیدگی کو O(n^4) تک کم کیا جا سکتا ہے۔
بٹ پیچیدگی، رسمی اصطلاحات میں، الگورتھم کو چلانے کے لیے درکار بٹس پر کارروائیوں کی تعداد سے مراد ہے۔ یہ دنیاوی پیچیدگی کو زیادہ تر حسابی نمونوں میں ایک مستقل عنصر تک برابر کرتا ہے۔ کمپیوٹر کو درکار مشینی الفاظ پر کارروائیوں کی تعداد بٹ پیچیدگی کے متناسب ہے۔ حساب کے حقیقت پسندانہ ماڈلز کے لیے، وقت کی پیچیدگی اور تھوڑی پیچیدگی ایک جیسی ہے۔
وسیلہ جو اکثر چھانٹنے اور تلاش کرنے میں سمجھا جاتا ہے وہ ہے اندراجات کے موازنہ کی مقدار۔ اگر ڈیٹا کو اچھی طرح سے ترتیب دیا گیا ہے، تو یہ وقت کی پیچیدگی کا ایک اچھا اشارہ ہے۔
تمام ممکنہ آدانوں پر، الگورتھم میں قدموں کی تعداد کو شمار کرنا ناممکن ہے۔ چونکہ ان پٹ کی پیچیدگی اس کے سائز کے ساتھ بڑھتی ہے، اس لیے اسے عام طور پر ان پٹ کے سائز n (بٹس میں) کے فنکشن کے طور پر ظاہر کیا جاتا ہے، اور اس لیے پیچیدگی n کا ایک فنکشن ہے۔ ایک ہی سائز کے ان پٹس کے لیے، تاہم، الگورتھم کی پیچیدگی کافی حد تک مختلف ہو سکتی ہے۔ نتیجے کے طور پر، مختلف قسم کے پیچیدگی کے افعال کو معمول کے مطابق استعمال کیا جاتا ہے۔
بدترین کیس کی پیچیدگی تمام سائز n ان پٹس کے لیے تمام پیچیدگیوں کا مجموعہ ہے، جب کہ اوسط کیس کی پیچیدگی تمام سائز n ان پٹس کے لیے تمام پیچیدگیوں کا مجموعہ ہے (یہ سمجھ میں آتا ہے، کیونکہ دیے گئے سائز کے ممکنہ ان پٹ کی تعداد محدود)۔ جب اصطلاح "پیچیدگی" کو مزید وضاحت کیے بغیر استعمال کیا جاتا ہے تو، بدترین کیس وقت کی پیچیدگی کو مدنظر رکھا جاتا ہے۔
بدترین کیس اور اوسط کیس کی پیچیدگی کا صحیح حساب لگانا بدنام زمانہ مشکل ہے۔ مزید برآں، ان درست اقدار کا عملی اطلاق بہت کم ہے کیونکہ مشین یا حساب کتاب کے پیراڈائم میں کوئی بھی تبدیلی پیچیدگی میں قدرے فرق کرے گی۔ مزید برآں، n کی چھوٹی اقدار کے لیے وسائل کا استعمال اہم نہیں ہے، اس لیے نفاذ میں آسانی چھوٹے n کے لیے کم پیچیدگی سے زیادہ دلکش ہوتی ہے۔
ان وجوہات کی بناء پر، سب سے زیادہ توجہ ہائی n کے لیے پیچیدگی کے رویے پر دی جاتی ہے، یعنی n کے لامحدودیت کے قریب آتے ہی اس کا غیر علامتی رویہ۔ نتیجے کے طور پر، بڑے O اشارے کو عام طور پر پیچیدگی کی نشاندہی کرنے کے لیے استعمال کیا جاتا ہے۔
کمپیوٹیشنل ماڈلز
کمپیوٹیشن ماڈل کا انتخاب، جس میں ضروری کارروائیوں کی وضاحت ہوتی ہے جو وقت کی اکائی میں انجام پاتے ہیں، پیچیدگی کا تعین کرنے کے لیے اہم ہے۔ اسے بعض اوقات ملٹی ٹیپ ٹورنگ مشین کہا جاتا ہے جب کمپیوٹیشن پیراڈائم کو خاص طور پر بیان نہیں کیا جاتا ہے۔
حساب کا ایک تعییناتی ماڈل وہ ہوتا ہے جس میں مشین کی بعد کی حالتیں اور انجام پانے والے آپریشن مکمل طور پر پچھلی حالت سے متعین ہوتے ہیں۔ تکراری فنکشنز، لیمبڈا کیلکولس، اور ٹورنگ مشینیں پہلے فیصلہ کن ماڈل تھیں۔ بے ترتیب رسائی والی مشینیں (جسے RAM مشینیں بھی کہا جاتا ہے) حقیقی دنیا کے کمپیوٹروں کی تقلید کے لیے ایک مشہور نمونہ ہے۔
جب کمپیوٹیشن ماڈل کی وضاحت نہیں کی جاتی ہے، تو عام طور پر ایک ملٹی ٹیپ ٹورنگ مشین فرض کی جاتی ہے۔ ملٹی ٹیپ ٹورنگ مشینوں پر، وقت کی پیچیدگی وہی ہے جو زیادہ تر الگورتھم کے لیے RAM مشینوں پر ہوتی ہے، حالانکہ اس مساوات کو حاصل کرنے کے لیے ڈیٹا کو میموری میں کیسے ذخیرہ کیا جاتا ہے اس پر کافی توجہ دینے کی ضرورت پڑ سکتی ہے۔
کمپیوٹنگ کے نان ڈیٹرمنسٹک ماڈل میں کمپیوٹنگ کے کچھ مراحل پر مختلف انتخاب کیے جا سکتے ہیں، جیسے نان ڈیٹرمنسٹک ٹورنگ مشین۔ پیچیدگی کے نظریہ میں، تمام ممکنہ اختیارات پر ایک ہی وقت میں غور کیا جاتا ہے، اور غیر متعین وقت کی پیچیدگی وہ وقت کی مقدار ہوتی ہے جب بہترین انتخاب ہمیشہ کیے جاتے ہیں۔ اسے ایک اور طریقے سے بیان کرنے کے لیے، حساب کتاب ایک ہی وقت میں جتنے (ایک جیسے) پروسیسرز کی ضرورت ہوتی ہے، کی جاتی ہے، اور نان ڈیٹرمنسٹک کمپیوٹیشن ٹائم وہ وقت ہوتا ہے جو پہلے پروسیسر نے کمپیوٹیشن کو مکمل کرنے میں لیا تھا۔ اس متوازی کوانٹم کمپیوٹنگ میں خصوصی کوانٹم الگورتھم چلاتے وقت سپرپوزڈ الجھی ہوئی حالتوں کا استعمال کرتے ہوئے استعمال کیا جا سکتا ہے، مثال کے طور پر چھوٹے عدد کو شور کی فیکٹرائزیشن۔
یہاں تک کہ اگر اس طرح کا شماریاتی ماڈل فی الحال قابل عمل نہیں ہے، اس کی نظریاتی اہمیت ہے، خاص طور پر P = NP مسئلے کے سلسلے میں، جو یہ پوچھتا ہے کہ کیا پیچیدگی کی کلاسیں "کثیراتی وقت" اور "غیر متعین کثیر نامی وقت" کے استعمال سے پیدا ہوتی ہیں؟ حدود ایک جیسے ہیں. ایک متعین کمپیوٹر پر، ایک NP-الگورتھم کی تقلید کے لیے "قطعی وقت" کی ضرورت ہوتی ہے۔ اگر کسی کام کو غیر متعین نظام پر کثیر وقت میں حل کیا جا سکتا ہے، تو اس کا تعلق NP مشکل طبقے سے ہے۔ اگر کوئی مسئلہ NP میں ہے اور کسی دوسرے NP مسئلے سے آسان نہیں ہے، تو اسے NP-مکمل کہا جاتا ہے۔ Knapsack مسئلہ، سفر کرنے والے سیلز مین کا مسئلہ، اور بولین اطمینان کا مسئلہ یہ تمام NP-مکمل امتزاج کے مسائل ہیں۔ سب سے مشہور الگورتھم میں ان تمام مسائل کے لیے کفایتی پیچیدگی ہے۔ اگر ان میں سے کوئی بھی مسئلہ تعییناتی مشین پر کثیر الثانی وقت میں حل کیا جا سکتا ہے، تو NP کے تمام مسائل بھی کثیر وقت میں حل ہو سکتے ہیں، اور P = NP قائم ہو جائے گا۔ 2017 تک، یہ بڑے پیمانے پر فرض کیا جاتا ہے کہ P NP، جس کا مطلب یہ ہے کہ NP کے مسائل کی بدترین صورت حال کو حل کرنا بنیادی طور پر مشکل ہے، یعنی دلچسپ ان پٹ طوالت کے پیش نظر کسی بھی قابل عمل مدت (دہائیوں) سے کہیں زیادہ وقت لگتا ہے۔
متوازی اور تقسیم شدہ کمپیوٹنگ
متوازی اور تقسیم شدہ کمپیوٹنگ میں متعدد پروسیسرز میں پروسیسنگ کو تقسیم کرنا شامل ہے جو سب ایک ہی وقت میں کام کرتے ہیں۔ مختلف ماڈلز کے درمیان بنیادی فرق پروسیسرز کے درمیان ڈیٹا بھیجنے کا طریقہ ہے۔ پروسیسرز کے درمیان ڈیٹا کی ترسیل عام طور پر متوازی کمپیوٹنگ میں بہت تیز ہوتی ہے، جب کہ تقسیم شدہ کمپیوٹنگ میں پروسیسرز کے درمیان ڈیٹا کی منتقلی پورے نیٹ ورک میں کی جاتی ہے اور اس طرح یہ کافی سست ہوتی ہے۔
N پروسیسرز پر شمار کرنے میں کم از کم حصہ N کے حساب سے ایک واحد پروسیسر پر لگتا ہے۔ حقیقت میں، کیونکہ کچھ ذیلی کاموں کو متوازی نہیں کیا جا سکتا ہے اور کچھ پروسیسرز کو دوسرے پروسیسر کے نتیجے کا انتظار کرنے کی ضرورت پڑ سکتی ہے، یہ نظریاتی طور پر مثالی حد کبھی حاصل نہیں ہو گی۔
اس طرح کلیدی پیچیدگی کا مسئلہ الگورتھم تیار کرنا ہے تاکہ پروسیسرز کی تعداد کے حساب سے کمپیوٹنگ کے وقت کی پیداوار کسی ایک پروسیسر پر ایک ہی کمپیوٹیشن کو انجام دینے کے لیے درکار وقت کے زیادہ سے زیادہ قریب ہو۔
کوانٹم کمپیوٹیشن
کوانٹم کمپیوٹر ایک ایسا کمپیوٹر ہے جس میں کوانٹم میکینکس پر مبنی کمپیوٹیشن ماڈل ہوتا ہے۔ چرچ – ٹورنگ تھیسس کوانٹم کمپیوٹرز کے لیے درست ہے، جس کا مطلب یہ ہے کہ کوئی بھی مسئلہ جسے کوانٹم کمپیوٹر حل کر سکتا ہے اسے ٹیورنگ مشین کے ذریعے بھی حل کیا جا سکتا ہے۔ تاہم، کچھ کاموں کو نظریاتی طور پر کلاسیکی کمپیوٹر کے بجائے کوانٹم کمپیوٹر کا استعمال کرتے ہوئے حل کیا جا سکتا ہے جس میں نمایاں طور پر کم وقتی پیچیدگی ہے۔ فی الحال، یہ سختی سے نظریاتی ہے، کیونکہ کوئی نہیں جانتا کہ عملی کوانٹم کمپیوٹر کیسے تیار کیا جائے۔
کوانٹم کمپلیکٹی تھیوری مختلف قسم کے مسائل کی تحقیقات کے لیے بنائی گئی تھی جو کوانٹم کمپیوٹرز کے ذریعے حل کیے جا سکتے ہیں۔ اس کا استعمال پوسٹ کوانٹم کرپٹوگرافی میں ہوتا ہے، جو کرپٹوگرافک پروٹوکول بنانے کا عمل ہے جو کوانٹم کمپیوٹر حملوں کے خلاف مزاحم ہیں۔
مسئلہ کی پیچیدگی (نچلی حد)
الگورتھم کی پیچیدگیوں کی انفیمم جو مسئلہ کو حل کر سکتی ہے، بشمول غیر دریافت شدہ تکنیک، مسئلہ کی پیچیدگی ہے۔ نتیجے کے طور پر، کسی مسئلے کی پیچیدگی کسی بھی الگورتھم کی پیچیدگی کے برابر ہے جو اسے حل کرتا ہے۔
نتیجے کے طور پر، بڑے O اشارے میں دی گئی کوئی بھی پیچیدگی الگورتھم اور اس کے ساتھ موجود مسئلہ دونوں کی پیچیدگی کی نمائندگی کرتی ہے۔
دوسری طرف، مسئلے کی پیچیدگی پر غیر معمولی نچلی حدوں کو حاصل کرنا اکثر مشکل ہوتا ہے، اور ایسا کرنے کے لیے کچھ حکمت عملی موجود ہیں۔
زیادہ تر مسائل کو حل کرنے کے لیے، تمام ان پٹ ڈیٹا کو پڑھنا ضروری ہے، جس میں ڈیٹا کی وسعت کے تناسب سے وقت لگتا ہے۔ نتیجے کے طور پر، اس طرح کے مسائل میں کم از کم لکیری پیچیدگی ہوتی ہے، یا بڑے اومیگا اشارے میں، Ω(n) کی پیچیدگی ہوتی ہے۔
کچھ مسائل، جیسے کہ کمپیوٹر الجبرا اور کمپیوٹیشنل الجبری جیومیٹری میں، بہت بڑے حل ہوتے ہیں۔ چونکہ آؤٹ پٹ کو لکھا جانا ضروری ہے، پیچیدگی آؤٹ پٹ کے زیادہ سے زیادہ سائز کی طرف سے محدود ہے.
چھانٹنے والے الگورتھم کے لیے درکار تقابل کی تعداد میں Ω(nlogn) کی غیر لکیری نچلی حد ہوتی ہے۔ نتیجے کے طور پر، بہترین ترتیب دینے والے الگورتھم سب سے زیادہ موثر ہیں کیونکہ ان کی پیچیدگی O(nlogn) ہے۔ حقیقت یہ ہے کہ ن ہیں! چیزوں کو منظم کرنے کے طریقے اس نچلی حد کی طرف لے جاتے ہیں۔ کیونکہ ہر ایک موازنہ ن کے اس مجموعہ کو تقسیم کرتا ہے! آرڈرز کو دو ٹکڑوں میں تقسیم کریں، تمام آرڈرز کو الگ کرنے کے لیے درکار N موازنہ کی تعداد 2N > n! ہونی چاہیے، جس کا مطلب سٹرلنگ کے فارمولے سے O(nlogn) ہے۔
کسی مسئلے کو دوسرے مسئلے تک کم کرنا پیچیدہ رکاوٹوں کو کم کرنے کے لیے ایک مشترکہ حکمت عملی ہے۔
الگورتھم کی ترقی
الگورتھم کی پیچیدگی کا اندازہ لگانا ڈیزائن کے عمل کا ایک اہم عنصر ہے کیونکہ یہ اس کارکردگی کے بارے میں مفید معلومات فراہم کرتا ہے جس کی توقع کی جا سکتی ہے۔
یہ ایک اکثر غلط فہمی ہے کہ مور کے قانون کے نتیجے میں، جو کہ جدید کمپیوٹر پاور کی تیز رفتار ترقی کی پیش گوئی کرتا ہے، الگورتھم کی پیچیدگی کا جائزہ لینا کم متعلقہ ہو جائے گا۔ یہ غلط ہے کیونکہ بڑھتی ہوئی طاقت بہت زیادہ ڈیٹا (بڑے ڈیٹا) کی پروسیسنگ کی اجازت دیتی ہے۔ مثال کے طور پر، کسی بھی الگورتھم کو ایک سیکنڈ سے بھی کم وقت میں اچھی طرح سے کام کرنا چاہیے جب حروف تہجی کے لحاظ سے چند سینکڑوں اندراجات کی فہرست کو ترتیب دیا جائے، جیسے کسی کتاب کی کتابیات۔ دوسری طرف، ایک ملین اندراجات (مثال کے طور پر، ایک بڑے شہر کے فون نمبر) کے لیے، بنیادی الگورتھم جن کے لیے O(n2) موازنہ کی ضرورت ہوتی ہے، انہیں ایک ٹریلین موازنے کرنے ہوں گے، جس میں 10 کی رفتار سے تین گھنٹے لگیں گے۔ فی سیکنڈ ملین موازنہ Quicksort اور merge sort، دوسری طرف، صرف nlogn موازنہ کی ضرورت ہوتی ہے (سابقہ کے لیے اوسط کیس کی پیچیدگی کے طور پر، بعد کے لیے بدترین کیس کی پیچیدگی کے طور پر)۔ یہ n = 30,000,000 کے لیے تقریباً 1,000,000 موازنے پیدا کرتا ہے، جس میں 3 ملین موازنہ فی سیکنڈ میں صرف 10 سیکنڈ لگیں گے۔
نتیجے کے طور پر، پیچیدگی کا اندازہ لگانے سے نفاذ سے پہلے بہت سے غیر موثر الگورتھم کو ختم کرنے کی اجازت مل سکتی ہے۔ یہ پیچیدہ الگورتھم کو ٹھیک کرنے کے لیے بھی استعمال کیا جا سکتا ہے بغیر تمام ممکنہ مختلف حالتوں کو جانچے۔ پیچیدگی کا مطالعہ ایک پیچیدہ الگورتھم کے انتہائی مہنگے مراحل کا تعین کرکے عمل درآمد کی کارکردگی کو بڑھانے کی کوششوں پر توجہ مرکوز کرنے کی اجازت دیتا ہے۔
سرٹیفیکیشن کے نصاب سے اپنے آپ کو تفصیل سے آشنا کرنے کے لیے آپ نیچے دی گئی جدول کو بڑھا سکتے ہیں اور اس کا تجزیہ کر سکتے ہیں۔
EITC/IS/CCTF کمپیوٹیشنل کمپلیکسٹی تھیوری فنڈامینٹلز سرٹیفیکیشن کریکولم ایک ویڈیو فارم میں کھلی رسائی کے تدریسی مواد کا حوالہ دیتا ہے۔ سیکھنے کے عمل کو مرحلہ وار ڈھانچے (پروگرام -> اسباق -> عنوانات) میں تقسیم کیا گیا ہے جس میں نصاب کے متعلقہ حصوں کا احاطہ کیا گیا ہے۔ ڈومین کے ماہرین کے ساتھ لامحدود مشاورت بھی فراہم کی جاتی ہے۔
سرٹیفیکیشن کے طریقہ کار کی تفصیلات کے لیے چیک کریں۔ یہ کیسے کام کرتا ہے.
بنیادی معاون نصاب پڑھنے کا مواد
ایس اروڑہ، بی بارک، کمپیوٹیشنل کمپلیکسیٹی: ایک جدید نقطہ نظر
https://theory.cs.princeton.edu/complexity/book.pdf
ثانوی معاون نصاب پڑھنے کا مواد
O. Goldreich، Introduction to Complexity Theory:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
مجرد ریاضی پر معاون نصاب پڑھنے کا مواد
J. Aspnes، مجرد ریاضی پر نوٹس:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
گراف تھیوری پر معاون نصاب پڑھنے کا مواد
آر ڈیسٹل، گراف تھیوری:
https://diestel-graph-theory.com/
EITC/IS/CCTF کمپیوٹیشنل کمپلیکسٹی تھیوری بنیادی پروگرام کے لیے مکمل آف لائن سیلف لرننگ تیاری کا مواد پی ڈی ایف فائل میں ڈاؤن لوڈ کریں۔
EITC/IS/CCTF تیاری کا مواد - معیاری ورژن
EITC/IS/CCTF تیاری کا مواد - جائزہ سوالات کے ساتھ توسیع شدہ ورژن