Betweenness
بیچینیس آرڈر تھیوری میں ایک الگورتھمک مسئلہ ہے جس میں اشیاء کے مجموعے کو آرڈر کرنے کے بارے میں پابندیوں کے تابع ہے کہ کچھ اشیاء کو دوسروں کے درمیان رکھنا ضروری ہے۔ اس کی بائیو انفارمیٹکس میں ایپلی کیشنز ہیں اور اسے این پی مکمل دکھایا گیا ہے۔ دشواری کا بیان بیچنے کے مسئلے کا ان پٹ آئٹمز کے آرڈرڈ ٹرپل کا مجموعہ ہے۔ ان ٹرپل میں درج آئٹمز کو کل ترتیب میں رکھا جانا چاہیے، اس خاصیت کے ساتھ کہ دیئے گئے ٹرپل میں سے ہر ایک کے لیے، ٹرپل میں درمیانی آئٹم آؤٹ پٹ میں دوسری دو آئٹمز کے درمیان کہیں ظاہر ہوتی ہے۔ ہر ٹرپل کی آئٹمز کا آؤٹ پٹ میں لگاتار ہونا ضروری نہیں ہے۔ مثال کے طور پر، ان پٹ ٹرپل (2,1,3)، (3,4,5)، (1,4,5)، (2,4,1)، (5,2,3) کا مجموعہ آؤٹ پٹ آرڈر 3، 1، 4، 2، 5 سے مطمئن ہوتا ہے لیکن 3، 1، 2، 4، 5 سے نہیں۔ ان آؤٹ پٹ ترتیبات میں سے پہلے میں، تمام پانچ ان پٹ ٹرپل کے لیے، ٹرپل کا درمیانی آئٹم دیگر دو آئٹمز کے درمیان ظاہر ہوتا ہے۔ تاہم، دوسرے آؤٹ پٹ ترتیب کے لیے، آئٹم 4 آئٹمز 1 اور 2 کے درمیان نہیں ہے، جو ٹرپل (2,4,1) کی طرف سے دی گئی ضرورت سے متصادم ہے۔ اگر کسی ان پٹ میں دو ٹرپل جیسے (1,2,3) اور (2,3,1) ایک ہی تین آئٹمز کے ساتھ ہیں لیکن درمیانی آئٹم کا مختلف انتخاب ہے، تو کوئی درست حل نہیں ہے۔ تاہم، بغیر کسی درست حل کے ٹرپل کا مجموعہ بنانے کے زیادہ پیچیدہ طریقے ہیں، جن میں اس طرح کے متضاد ٹرپل کا جوڑا نہیں ہوتا ہے۔ پیچیدگی سے پتہ چلتا ہے کہ بیچنے کے مسئلے کا فیصلہ ورژن (جس میں ایک الگورتھم کو یہ فیصلہ کرنا ہوگا کہ کوئی درست حل موجود ہے یا نہیں) این پی دو طریقوں سے مکمل ہے، 3-اطمینان سے کمی اور ہائپر گراف 2-رنگ سے مختلف کمی سے بھی۔ تاہم، اسے آسانی سے حل کیا جا سکتا ہے جب آئٹمز کے تمام غیر ترتیب شدہ ٹرپل کی نمائندگی ان پٹ کے آرڈرڈ ٹرپل کے ذریعے کی جاتی ہے، ان دو آئٹمز میں سے کسی ایک کو منتخب کرکے جو کسی اور کے درمیان نہیں ہے تاکہ آرڈر کا آغاز ہو اور پھر اس آئٹم میں شامل ٹرپل کا استعمال کرتے ہوئے بقیہ آئٹمز کے ہر جوڑے کی متعلقہ پوزیشنوں کا موازنہ کیا جا سکے۔ ایک ترتیب تلاش کرنے کا متعلقہ مسئلہ جو مطمئن ٹرپل کی تعداد کو زیادہ سے زیادہ کرتا ہے وہ MAXSNP-سخت ہے، جس کا مطلب ہے کہ کثیر الجہتی وقت میں من مانی طور پر 1 کے قریب تخمینہ تناسب حاصل کرنا ناممکن ہے جب تک کہ P = NP نہ ہو۔ یہاں تک کہ گھنے مثالوں کے لیے بھی اسے حل کرنا یا تخمینہ لگانا مشکل رہتا ہے جس میں ہر ممکنہ غیر ترتیب شدہ تین آئٹمز کے لیے ایک آرڈرڈ ٹرپل شامل ہوتا ہے۔ ٹورنامنٹ تک محدود مسئلے کے کم از کم ورژن میں کثیر الجہتی وقت تخمینہ اسکیمیں (پی ٹی اے ایس) ثابت ہوئی تھیں۔ اشیاء کو تصادفی طور پر ترتیب دے کر 1/3 (توقع میں) کا تخمینہ تناسب حاصل کیا جا سکتا ہے، اور یہ سادہ حکمت عملی بہترین ممکنہ کثیر الجہتی وقت کا تخمینہ دیتی ہے اگر منفرد گیم کا قیاس درست ہے۔ ایسی ترتیب تلاش کرنے کے لیے سیمی فائنائٹ پروگرامنگ یا مشترکہ طریقوں کا استعمال کرنا بھی ممکن ہے جو کثیر الجہتی وقت میں کسی بھی تسلی بخش مثال کے کم از کم نصف ٹرپل کو مطمئن کرے۔ پیرامیٹرائزڈ پیچیدگی میں، رکاوٹوں کے ایک سیٹ C سے زیادہ سے زیادہ رکاوٹوں کو پورا کرنے کا مسئلہ فکسڈ پیرامیٹر ٹریکٹیبل ہوتا ہے جب پیرامیٹرائزڈ الگورتھم کے ذریعہ پائے جانے والے حل کے معیار q اور بے ترتیب ترتیب کے ذریعہ توقع میں ضمانت شدہ |C |/3 معیار کے درمیان فرق q− |C |/3 کے ذریعہ پیرامیٹرائز کیا جاتا ہے۔ اگرچہ کامیاب ہونے کی ضمانت نہیں ہے، لیکن ایک لالچی محقق عملی طور پر پیدا ہونے والے بیچینی کے مسئلے کی بہت سی مثالوں کا حل تلاش کر سکتا ہے۔ ایپلی کیشنز جین میپنگ کے عمل کے حصے کے طور پر بائیو انفارمیٹکس میں بیچینیس کا ایک اطلاق پیدا ہوتا ہے۔ جینیاتی مارکر کے ٹرپل کی ترتیب کا تعین کرنے کے لیے بعض قسم کے جینیاتی تجربات استعمال کیے جا سکتے ہیں، لیکن جینیاتی ترتیب کو اس کے الٹ جانے سے الگ نہیں کرتے، اس لیے اس طرح کے تجربے سے حاصل ہونے والی معلومات صرف اس بات کا تعین کرتی ہے کہ تین میں سے کون سا مارکر درمیانی ہے۔ بیچنے کا مسئلہ اس قسم کے تجرباتی اعداد و شمار کو دیکھتے ہوئے مارکر کے مجموعے کو ایک ہی ترتیب میں جمع کرنے کے مسئلے کا خلاصہ ہے۔ بیچنے کا مسئلہ امکان، وجہ اور وقت کے نظریات کو ماڈل بنانے کے لیے بھی استعمال کیا گیا ہے۔ حوالہ جات این پی مکمل مسائل آرڈر تھیوری