Partition problem
نمبر تھیوری اور کمپیوٹر سائنس میں، پارٹیشن کا مسئلہ، یا نمبر پارٹیشننگ، یہ فیصلہ کرنے کا کام ہے کہ آیا مثبت انٹیجرز کے دیئے گئے ملٹی سیٹ S کو دو ذیلی سیٹوں S1 اور S2 میں تقسیم کیا جا سکتا ہے تاکہ S1 میں نمبروں کا مجموعہ S2 میں موجود نمبروں کے مجموعے کے برابر ہو۔ اگرچہ تقسیم کا مسئلہ این پی مکمل ہے، لیکن ایک فرضی کثیر الجہتی وقت متحرک پروگرامنگ حل موجود ہے، اور ایسی تحقیقات موجود ہیں جو بہت سے معاملات میں مسئلے کو بہتر یا تقریبا حل کرتی ہیں۔ اس وجہ سے اسے "سب سے آسان مشکل مسئلہ" کہا گیا ہے۔ تقسیم کے مسئلے کا ایک اصلاح ورژن ہے، جو ملٹی سیٹ S کو دو ذیلی سیٹوں S1، S2 میں تقسیم کرنا ہے تاکہ S1 میں عناصر کے مجموعے اور S2 میں عناصر کے مجموعے کے درمیان فرق کو کم سے کم کیا جائے۔ اصلاح کا ورژن این پی سخت ہے، لیکن اسے عملی طور پر مؤثر طریقے سے حل کیا جا سکتا ہے۔ تقسیم کا مسئلہ دو متعلقہ مسائل کا ایک خاص معاملہ ہے: سب سیٹ سم کے مسئلے میں، مقصد S کا ایک سب سیٹ تلاش کرنا ہے جس کا مجموعہ ایک مخصوص ہدف نمبر T ہے جسے ان پٹ کے طور پر دیا گیا ہے (تقسیم کا مسئلہ وہ خاص معاملہ ہے جس میں T S کا نصف مجموعہ ہے)۔ ملٹی وے نمبر پارٹیشننگ میں، ایک انٹیجر پیرامیٹر k ہوتا ہے، اور مقصد یہ فیصلہ کرنا ہے کہ آیا S کو مساوی رقم کے k ذیلی سیٹوں میں تقسیم کیا جا سکتا ہے (پارٹیشن کا مسئلہ وہ خاص معاملہ ہے جس میں k = 2)۔ تاہم، یہ 3-پارٹیشن کے مسئلے سے بالکل مختلف ہے: اس مسئلے میں، ذیلی سیٹوں کی تعداد پہلے سے طے نہیں کی جاتی ہے-یہ |S |/3 ہونی چاہیے، جہاں ہر ذیلی سیٹ میں بالکل 3 عناصر ہونے چاہئیں۔ 3-تقسیم تقسیم سے کہیں زیادہ مشکل ہے-اس میں کوئی فرضی کثیر الجہتی وقت الگورتھم نہیں ہے جب تک کہ P = NP نہ ہو۔ S = {3,1,1، 2,2,1} دی گئی مثالیں، تقسیم کے مسئلے کا ایک درست حل دو سیٹ S1 = {1,1,1، 2} اور S2 = {{2,3} ہیں۔ دونوں سیٹوں کا مجموعہ 5 ہے، اور وہ S کو تقسیم کرتے ہیں۔ نوٹ کریں کہ یہ حل منفرد نہیں ہے۔ S1 = {3,1,1} اور S2 = {2,2,1} ایک اور حل ہے۔ مثبت انٹیجرز کے ہر ملٹی سیٹ میں مساوی رقم کے ساتھ دو ذیلی سیٹوں میں تقسیم نہیں ہوتا ہے۔ اس طرح کے سیٹ کی ایک مثال S = {2,5} ہے۔ کمپیوٹیشنل سختی تقسیم کا مسئلہ این پی سخت ہے۔ یہ سب سیٹ سم کے مسئلے کو کم کرکے ثابت کیا جا سکتا ہے۔ سب سیٹ سم کی ایک مثال مثبت انٹیجرز کے ایک سیٹ S اور ایک ٹارگٹ سم T پر مشتمل ہوتی ہے۔ مقصد یہ طے کرنا ہے کہ آیا S کا کوئی سب سیٹ ہے جس کا مجموعہ بالکل T ہے۔ ایسی مثال کو دیکھتے ہوئے، پارٹیشن کی ایک مثال بنائیں جس میں ان پٹ سیٹ میں اصل سیٹ کے علاوہ دو عناصر: z1 اور z2 ہوں، جس میں z1 = sum (S) اور z2 = 2T ہوں۔ اس ان پٹ سیٹ کا مجموعہ مجموعہ (S) + z1 + z2 = 2 مجموعہ (S) + 2T ہے، لہذا پارٹیشن کے لیے ہدف کا مجموعہ مجموعہ (S) + T ہے۔ فرض کریں کہ سب سیٹ سم مثال کا حل S′ موجود ہے۔ پھر مجموعہ (S′) = T، تو مجموعہ (S′z _ 1) = مجموعہ (S) + T، تو S′z _ 1 تقسیم کی مثال کا حل ہے۔ اس کے برعکس، فرض کریں کہ تقسیم کی مثال کا کوئی حل S "موجود ہے۔ پھر، S′ میں یا تو z1 یا z2 ہونا چاہیے، لیکن دونوں نہیں، کیونکہ ان کا مجموعہ مجموعہ (S) + T سے زیادہ ہے۔ اگر S "میں z1 ہے، تو اس میں S کے عناصر بالکل T کے مجموعے کے ساتھ ہونے چاہئیں، لہذا S" مائنس z1 سب سیٹ سم مثال کا حل ہے۔ اگر S "میں z2 موجود ہے، تو اس میں S کے عناصر کو بالکل مجموعہ (S) − T کے ساتھ ہونا چاہیے، لہذا S میں موجود دیگر اشیاء سب سیٹ سم مثال کا حل ہیں۔ جیسا کہ اوپر ذکر کیا گیا ہے، پارٹیشن کا مسئلہ ملٹی وے پارٹیشننگ اور سب سیٹ سم کا ایک خاص معاملہ ہے۔ لہذا، ان میں سے ہر ایک مسئلے کے لیے تیار کردہ الگورتھم کے ذریعے اسے حل کیا جا سکتا ہے۔ ملٹی وے نمبر پارٹیشننگ کے لیے تیار کردہ الگورتھم میں شامل ہیں: لالچی نمبر پارٹیشننگ-نمبروں پر لوپ کرتا ہے، اور ہر نمبر کو اس سیٹ میں رکھتا ہے جس کا موجودہ مجموعہ سب سے چھوٹا ہے۔ اگر اعداد کو ترتیب نہیں دیا جاتا ہے، تو رن ٹائم O (n) ہے اور تخمینہ تناسب زیادہ سے زیادہ 3/2 ہے ("تخمینہ تناسب" کا مطلب الگورتھم آؤٹ پٹ میں بڑی رقم ہے، جسے زیادہ سے زیادہ تقسیم میں بڑی رقم سے تقسیم کیا جاتا ہے)۔ نمبروں کو ترتیب دینے سے رن ٹائم بڑھ کر O (n لاگ n) ہو جاتا ہے اور تخمینہ تناسب 7/6 ہو جاتا ہے۔ اگر اعداد کو یکساں طور پر [0,1] میں تقسیم کیا جاتا ہے، تو تخمینہ کا تناسب زیادہ سے زیادہ تقریبا یقینی طور پر اور توقع میں ہوتا ہے۔ سب سے بڑا تفریق کا طریقہ (جسے کرمارکر-کارپ الگورتھم بھی کہا جاتا ہے) نمبروں کو نزولی ترتیب میں ترتیب دیتا ہے اور بار بار ان کے فرق سے نمبروں کی جگہ لے لیتا ہے۔ رن ٹائم کی پیچیدگی O (n لاگ n) ہے۔ بدترین صورت میں، اس کا تخمینہ تناسب یکساں ہے-زیادہ سے زیادہ 7/6۔ تاہم، اوسط صورت میں یہ لالچی الگورتھم سے بہت بہتر کارکردگی کا مظاہرہ کرتا ہے: جب اعداد کو [0,1] میں یکساں طور پر تقسیم کیا جاتا ہے، تو اس کا تخمینہ تناسب زیادہ سے زیادہ توقع میں ہوتا ہے۔ یہ تخروپن تجربات میں بھی بہتر کارکردگی کا مظاہرہ کرتا ہے۔ ملٹی فٹ الگورتھم بن پیکنگ کے لیے الگورتھم کے ساتھ مل کر بائنری سرچ کا استعمال کرتا ہے۔ بدترین صورت میں، اس کا تخمینہ تناسب 8/7 ہے۔ سب سیٹ سم کے مسئلے میں ایک ایف پی ٹی اے ایس ہوتا ہے جسے تقسیم کے مسئلے کے لیے بھی استعمال کیا جا سکتا ہے، ہدف کی رقم کو جمع (ایس)/2 مقرر کرکے۔ عین مطابق الگورتھم درست الگورتھم ہوتے ہیں، جو ہمیشہ بہترین پارٹیشن تلاش کرتے ہیں۔ چونکہ مسئلہ این پی سخت ہے، اس طرح کے الگورتھم میں عام طور پر تیز رفتار وقت لگ سکتا ہے، لیکن بعض صورتوں میں عملی طور پر قابل استعمال ہو سکتا ہے۔ ملٹی وے نمبر پارٹیشننگ کے لیے تیار کردہ الگورتھم میں شامل ہیں: سیڈوپولینومیل ٹائم نمبر پارٹیشننگ میموری لیتا ہے، جہاں ان پٹ میں سب سے بڑا نمبر ہوتا ہے۔ مکمل لالچ الگورتھم (سی جی اے) بائنری ٹری بنا کر تمام پارٹیشنوں پر غور کرتا ہے۔ درخت میں ہر سطح ایک ان پٹ نمبر سے مطابقت رکھتی ہے، جہاں جڑ سب سے بڑی تعداد سے مطابقت رکھتی ہے، نیچے کی سطح اگلی سب سے بڑی تعداد وغیرہ سے مطابقت رکھتی ہے۔ ہر شاخ ایک مختلف سیٹ سے مطابقت رکھتی ہے جس میں موجودہ نمبر ڈالا جا سکتا ہے۔ درخت کو گہرائی-پہلی ترتیب میں عبور کرنے کے لیے صرف جگہ کی ضرورت ہوتی ہے، لیکن اس میں وقت لگ سکتا ہے۔ لالچی ہیورسٹک کا استعمال کرکے رن ٹائم کو بہتر بنایا جا سکتا ہے: ہر سطح میں، پہلے وہ شاخ تیار کریں جس میں موجودہ نمبر کو سب سے چھوٹی رقم کے ساتھ سیٹ میں رکھا جائے۔ یہ الگورتھم پہلے لالچی نمبر پارٹیشننگ کے ذریعے پایا جانے والا حل تلاش کرتا ہے، لیکن پھر بہتر حل تلاش کرنے کے لیے آگے بڑھتا ہے۔ اس خیال کے کچھ تغیرات ذیلی سیٹ-سم کے مسئلے کے لیے مکمل طور پر کثیر الجہتی وقت کے تخمینے کی اسکیمیں ہیں، اور اسی وجہ سے تقسیم کے مسئلے کے لیے بھی۔ مکمل کرمارکر-کارپ الگورتھم (سی کے کے) بائنری ٹری بنا کر تمام پارٹیشنوں پر غور کرتا ہے۔ ہر سطح اعداد کے جوڑے سے مطابقت رکھتی ہے۔ بائیں شاخ انہیں مختلف ذیلی سیٹوں میں ڈالنے سے مطابقت رکھتی ہے (یعنی، ان کے فرق سے ان کی جگہ لے لیتی ہے)، اور دائیں شاخ انہیں ایک ہی ذیلی سیٹ میں رکھنے سے مطابقت رکھتی ہے (یعنی، ان کی جگہ ان کے مجموعے سے)۔ یہ الگورتھم پہلے سب سے بڑے تفریق کے طریقے سے پایا جانے والا حل تلاش کرتا ہے، لیکن پھر بہتر حل تلاش کرنے کے لیے آگے بڑھتا ہے۔ یہ بے ترتیب مثالوں پر سی جی اے سے کافی تیزی سے چلتا ہے۔ جب مساوی تقسیم موجود ہو تو اس کا فائدہ بہت زیادہ ہوتا ہے، اور یہ شدت کے کئی آرڈرز کا ہو سکتا ہے۔ عملی طور پر، صوابدیدی سائز کے مسائل کو سی کے کے کے ذریعے حل کیا جا سکتا ہے اگر اعداد میں زیادہ سے زیادہ 12 اہم ہندسوں ہوں۔ سی کے کے کسی بھی وقت الگورتھم کے طور پر بھی چل سکتا ہے: یہ پہلے کے کے حل تلاش کرتا ہے، اور پھر وقت کی اجازت کے ساتھ بتدریج بہتر حل تلاش کرتا ہے (ممکنہ طور پر زیادہ سے زیادہ وقت تک پہنچنے کے لیے، بدترین مثالوں کے لیے)۔ اس کے لیے جگہ درکار ہوتی ہے، لیکن بدترین صورت میں اس میں وقت لگ سکتا ہے۔ سب سیٹ سم کے لیے تیار کردہ الگورتھم میں شامل ہیں: ہورووٹز اور سانہی-وقت پر چلتے ہیں، لیکن جگہ درکار ہوتی ہے۔ شروپل اور شمیر-وقت پر دوڑتے ہیں، اور بہت کم جگہ کی ضرورت ہوتی ہے۔ ہاؤگریو-گراہم اور جوکس-وقت کے ساتھ چلتا ہے، لیکن یہ ایک بے ترتیب الگورتھم ہے جو صرف فیصلے کے مسئلے کو حل کرتا ہے (اصلاح کا مسئلہ نہیں)۔ مشکل مثالیں اور فیز ٹرانزیشن سیٹ جن میں صرف ایک ہے، یا کوئی پارٹیشن نہیں ہے، ان کے ان پٹ سائز کے مقابلے میں حل کرنا سب سے مشکل (یا سب سے مہنگا) ہوتا ہے۔ جب سیٹ کے سائز کے مقابلے میں اقدار چھوٹی ہوتی ہیں، تو کامل پارٹیشن کا امکان زیادہ ہوتا ہے۔ یہ مسئلہ "فیز ٹرانزیشن" سے گزرنے کے لیے جانا جاتا ہے ؛ کچھ سیٹوں کے لیے امکان اور دوسروں کے لیے امکان نہیں۔ اگر m سیٹ میں کسی بھی نمبر کو ظاہر کرنے کے لیے درکار بٹس کی تعداد ہے اور n سیٹ کا سائز ہے تو اس میں بہت سے حل ہوتے ہیں اور ان کا حل کم یا کوئی نہیں ہوتا ہے۔ جیسے جیسے n اور m بڑے ہوتے جاتے ہیں، کامل تقسیم کا امکان بالترتیب 1 یا 0 ہوتا جاتا ہے۔ یہ اصل میں جینٹ اور والش کے تجرباتی شواہد کی بنیاد پر استدلال کیا گیا تھا، پھر مرٹنز کے ذریعہ شماریاتی طبیعیات کے طریقوں کا استعمال کرتے ہوئے، اور بعد میں بورگس، چیس اور پیٹل نے ثابت کیا۔ ممکنہ ورژن ایک متعلقہ مسئلہ، جو کچھ حد تک برتھ ڈے پیراڈوکس سے ملتا جلتا ہے، وہ ہے ان پٹ سیٹ کے سائز کا تعین کرنا تاکہ ہمارے پاس نصف کا امکان ہو کہ کوئی حل ہو، اس مفروضے کے تحت کہ سیٹ میں موجود ہر عنصر کو تصادفی طور پر 1 اور کچھ دی گئی قیمت کے درمیان یکساں تقسیم کے ساتھ منتخب کیا گیا ہے۔ اس مسئلے کا حل برتھ ڈے پیراڈوکس کی طرح متضاد ہو سکتا ہے۔ متغیرات اور عمومی مساوات ایک متغیر ہے جس میں دونوں حصوں میں مساوی رقم کے علاوہ اشیاء کی مساوی تعداد ہونی چاہیے۔ یہ قسم بھی این پی سخت ہے۔ ثبوت۔ کچھ n نمبروں کے ساتھ ایک معیاری پارٹیشن کی مثال کو دیکھتے ہوئے، n صفر کا اضافہ کرکے ایک مساوی-کارڈینیلیٹی-پارٹیشن کی مثال بنائیں۔ واضح طور پر، نئی مثال میں ایک مساوی-کارڈینیلیٹی مساوی-رقم تقسیم ہے اگر اصل مثال میں مساوی-رقم تقسیم ہے۔ متوازن نمبر پارٹیشننگ بھی دیکھیں۔ مخصوص پارٹیشن ایک مختلف قسم ہے جس میں تمام ان پٹ انٹیجر الگ ہوتے ہیں۔ یہ قسم بھی این پی سخت ہے۔ پروڈکٹ پارٹیشن انٹیجرز کے ایک سیٹ کو ایک ہی پروڈکٹ (ایک ہی رقم کے بجائے) کے ساتھ دو سیٹوں میں تقسیم کرنے کا مسئلہ ہے۔ یہ مسئلہ سختی سے این پی سخت ہے۔ کووالیوف اور پیسچ تقسیم کی قسم کے مسائل کی این پی سختی کو ثابت کرنے کے لیے ایک عام نقطہ نظر پر تبادلہ خیال کرتے ہیں۔ ایپلی کیشنز تقسیم کے مسئلے کا ایک اطلاق انتخابات میں ہیرا پھیری کے لیے ہے۔ فرض کریں کہ تین امیدوار (اے، بی اور سی) ہیں۔ ایک واحد امیدوار کو اسکورنگ کی بنیاد پر ووٹنگ کے اصول کا استعمال کرتے ہوئے منتخب کیا جانا چاہیے، جیسے۔ ویٹو رول (ہر ووٹر ایک امیدوار کو ویٹو کرتا ہے اور سب سے کم ویٹو والا امیدوار جیت جاتا ہے)۔ اگر کوئی اتحاد اس بات کو یقینی بنانا چاہتا ہے کہ سی منتخب ہو، تو اسے اپنے ووٹوں کو اے اور بی کے درمیان تقسیم کرنا چاہیے تاکہ ان میں سے ہر ایک کو ملنے والے ویٹو کی سب سے کم تعداد کو زیادہ سے زیادہ کیا جا سکے۔ اگر ووٹوں کا وزن کیا جاتا ہے، تو اس مسئلے کو تقسیم کے مسئلے تک کم کیا جا سکتا ہے، اور اس طرح اسے سی کے کے کا استعمال کرتے ہوئے مؤثر طریقے سے حل کیا جا سکتا ہے۔ اسکورنگ پر مبنی ووٹنگ کے کسی بھی دوسرے اصول کے لیے بھی یہی بات درست ہے۔ نوٹ حوالہ جات نمبر پارٹیشننگ کمزور این پی مکمل مسائل