Pseudo-polynomial time
کمپیوٹیشنل پیچیدگی کے نظریہ میں، ایک عددی الگورتھم فرضی کثیر الجہتی وقت میں چلتا ہے اگر اس کا چلنے کا وقت ان پٹ کی عددی قدر میں کثیر الجہتی ہے (ان پٹ میں موجود سب سے بڑا عدد)-لیکن ضروری نہیں کہ ان پٹ کی لمبائی میں ہو (اس کی نمائندگی کے لیے درکار بٹس کی تعداد)، جو کہ کثیر الجہتی وقت کے الگورتھم کا معاملہ ہے۔ عام طور پر، ان پٹ کی عددی قیمت ان پٹ کی لمبائی میں ایکسپونینشل ہوتی ہے، یہی وجہ ہے کہ ایک فرضی کثیر الجہتی وقت الگورتھم لازمی طور پر ان پٹ کی لمبائی کے حوالے سے کثیر الجہتی وقت میں نہیں چلتا ہے۔ معروف چھدم کثیر الجہتی وقت کے الگورتھم کے ساتھ ایک این پی مکمل مسئلہ کو کمزور این پی مکمل کہا جاتا ہے۔ این پی مکمل مسئلے کو مضبوطی سے این پی مکمل کہا جاتا ہے اگر یہ ثابت ہو جائے کہ اسے فرضی کثیر الجہتی ٹائم الگورتھم کے ذریعے حل نہیں کیا جا سکتا جب تک کہ۔ این پی سختی کی مضبوط/کمزور اقسام کو یکساں طور پر بیان کیا گیا ہے۔ ابتدائی جانچ کی مثالیں یہ جانچنے کے مسئلے پر غور کریں کہ آیا نمبر n پرائم ہے، بے وقوفانہ طور پر یہ جانچ کر کے کہ آیا کوئی نمبر یکساں طور پر تقسیم نہیں ہوتا ہے۔ یہ نقطہ نظر تقسیم تک لے جا سکتا ہے، جو کہ n کی قدر میں ذیلی لکیری ہے لیکن n کی لمبائی میں ایکسپونینشل ہے (جو تقریبا ہے)۔ مثال کے طور پر، n سے قدرے کم نمبر کے لیے تقریبا 100,000 ڈویژنوں کی ضرورت ہوگی، حالانکہ n کی لمبائی صرف 11 ہندسوں کی ہے۔ اس کے علاوہ کوئی بھی آسانی سے ایک ان پٹ (جیسے 300 ہندسوں کا نمبر) لکھ سکتا ہے جس کے لیے یہ الگورتھم ناقابل عمل ہے۔ چونکہ کمپیوٹیشنل پیچیدگی (انکوڈڈ) ان پٹ کی لمبائی کے حوالے سے مشکل کی پیمائش کرتی ہے، اس لیے یہ سادہ الگورتھم دراصل ایکسپونینشل ہے۔ تاہم، یہ فرضی کثیر الجہتی وقت ہے۔ اس الگورتھم کا موازنہ ایک حقیقی کثیر الجہتی عددی الگورتھم سے کریں-فرض کریں، اضافے کے لیے سیدھا الگورتھم: دو 9 ہندسوں کے نمبروں کو شامل کرنے میں تقریبا 9 آسان اقدامات لگتے ہیں، اور عام طور پر الگورتھم واقعی ان پٹ کی لمبائی میں لکیری ہوتا ہے۔ شامل کیے جانے والے اصل اعداد (اربوں میں) کے مقابلے میں، الگورتھم کو "سیوڈو-لوگرتھمک ٹائم" کہا جا سکتا ہے، حالانکہ ایسی اصطلاح معیاری نہیں ہے۔ اس طرح 300 ہندسوں کے اعداد کا اضافہ کرنا ناقابل عمل نہیں ہے۔ اسی طرح، لمبی تقسیم کواڈریٹک ہے: ایک ایم ہندسوں کے نمبر کو مراحل میں این ہندسوں کے نمبر سے تقسیم کیا جا سکتا ہے (بگ او نوٹیشن دیکھیں۔) پرائملٹی کے معاملے میں، یہ پتہ چلتا ہے کہ یہ جانچنے کے لیے ایک مختلف الگورتھم موجود ہے کہ آیا n پرائم ہے (2002 میں دریافت کیا گیا) جو وقت کے ساتھ چلتا ہے۔ نیپسیک کا مسئلہ نیپسیک کے مسئلے میں، ہمیں وزن اور قیمت کے ساتھ ساتھ نیپسیک کی زیادہ سے زیادہ وزن کی گنجائش والی اشیاء دی جاتی ہیں۔ مقصد مندرجہ ذیل اصلاح کے مسئلے کو حل کرنا ہے ؛ غیر رسمی طور پر، زیادہ سے زیادہ قیمت کے لیے اشیاء کو نیپسیک میں فٹ کرنے کا بہترین طریقہ کیا ہے؟ سبجیکٹ اور کو زیادہ سے زیادہ کریں۔ اس مسئلے کو حل کرنا این پی-سخت ہے، لہذا ایک کثیر الجہتی ٹائم الگورتھم ناممکن ہے جب تک کہ. تاہم، متحرک پروگرامنگ کا استعمال کرتے ہوئے ایک ٹائم الگورتھم ممکن ہے ؛ چونکہ نمبر کو بیان کرنے کے لیے صرف بٹس کی ضرورت ہوتی ہے، اس لیے یہ الگورتھم فرضی کثیر الجہتی وقت میں چلتا ہے۔ اگرچہ فرضی کثیر الجہتی وقت کا تصور تقریبا خصوصی طور پر عددی مسائل کے لیے استعمال ہوتا ہے، اس تصور کو عمومی بنایا جا سکتا ہے: فنکشن m فرضی کثیر الجہتی ہے اگر m (n) مسئلہ سائز n کے کثیر الجہتی فنکشن سے بڑا نہیں ہے اور ان پٹ کی ایک اضافی خاصیت، k (n) ہے۔ (ممکنہ طور پر، k کو مسئلہ سے متعلق چیز کے طور پر منتخب کیا گیا ہے۔) یہ k کو ان پٹ کی عددی قدر بنا کر عددی کثیر الجہتی مسائل کو ایک خاص معاملہ بناتا ہے۔ کسی عدد کی قدر اور اس کی لمبائی کے درمیان فرق انکوڈنگ میں سے ایک ہے: اگر عددی ان پٹ کو ہمیشہ یونری میں انکوڈ کیا جاتا ہے، تو چھدم-کثیر الجہتی کثیر الجہتی کے ساتھ موافق ہوگا۔ مضبوط این پی مکمل نیم کثیر الجہتی وقت کے حوالہ جات الگورتھم کا تجزیہ پیچیدگی کلاسیں کمپیوٹیشنل پیچیدگی تھیوری فرضی کثیر الجہتی وقت کے الگورتھم بھی دیکھیں۔