Pseudo-Boolean function
ریاضی اور اصلاح میں، ایک چھدم-بولین فنکشن اس شکل کا ایک فنکشن ہے جہاں ایک بولین ڈومین ہے اور یہ ایک غیر منفی عدد ہے جسے فنکشن کی آرٹی کہا جاتا ہے۔ بولین فنکشن پھر ایک خاص معاملہ ہوتا ہے، جہاں اقدار بھی 0 یا 1 تک محدود ہوتی ہیں۔ نمائندگی کسی بھی چھدم-بولین فنکشن کو کثیر لکیری کثیر الجہتی کے طور پر منفرد طور پر لکھا جا سکتا ہے: چھدم-بولین فنکشن کی ڈگری محض اس نمائندگی میں کثیر الجہتی کی ڈگری ہے۔ بہت سی ترتیبات میں (مثال کے طور پر، چھدم-بولین افعال کے فورئیر تجزیے میں)، ایک چھدم-بولین فنکشن کو ایک فنکشن کے طور پر دیکھا جاتا ہے جو نقشہ بناتا ہے۔ ایک بار پھر اس معاملے میں ہم منفرد طور پر ایک کثیر لکیری کثیر الجہتی کے طور پر لکھ سکتے ہیں: اور کے فورئیر گتانک کہاں ہیں۔ اصلاح کم سے کم کرنا (یا، مساوی طور پر، زیادہ سے زیادہ کرنا) ایک فرضی بولین فنکشن این پی-ہارڈ ہے۔ یہ آسانی سے تشکیل دے کر دیکھا جا سکتا ہے، مثال کے طور پر، زیادہ سے زیادہ کٹ کا مسئلہ چھدم-بولین فنکشن کو زیادہ سے زیادہ کرنے کے طور پر۔ سب ماڈیولرٹی سب ماڈیولر سیٹ فنکشنز کو سیڈو-بولین فنکشنز کی ایک خاص کلاس کے طور پر دیکھا جا سکتا ہے، جو اس شرط کے مساوی ہے۔ یہ سیڈو-بولین فنکشنز کی ایک اہم کلاس ہے، کیونکہ انہیں کثیر الجہتی وقت میں کم سے کم کیا جا سکتا ہے۔ نوٹ کریں کہ سب ماڈیولر فنکشن کو کم سے کم کرنا ایک کثیر الجہتی حل طلب مسئلہ ہے جو پریزنٹیشن فارم پر آزاد ہے، مثال کے طور پر۔ پیسوڈو-بولین کثیر الجہتی، ایک ذیلی ماڈیولر فنکشن کو زیادہ سے زیادہ کرنے کے برعکس جو کہ NP-سخت ہے، الیگزینڈر شریجور (2000)۔ چھت دوہری اگر f ایک مربع کثیر الجہتی ہے، تو چھت دوہری نامی تصور کو اس کی کم سے کم قیمت کے لیے نچلی حد حاصل کرنے کے لیے استعمال کیا جا سکتا ہے۔ چھت کی دوہری حیثیت متغیرات کی جزوی تفویض بھی فراہم کر سکتی ہے، جو کثیر الجہتی کو کم سے کم کرنے والے کی کچھ اقدار کی نشاندہی کرتی ہے۔ نچلی حدود حاصل کرنے کے کئی مختلف طریقے صرف تیار کیے گئے تھے جنہیں بعد میں اس کے مساوی دکھایا گیا جسے اب چھت کی دوہری حیثیت کہا جاتا ہے۔ اگر f کی ڈگری 2 سے زیادہ ہے، تو کوئی بھی اضافی متغیرات کے ساتھ مساوی کواڈریٹک مسئلہ حاصل کرنے کے لیے ہمیشہ کمی کا استعمال کر سکتا ہے۔ ایک ممکنہ کمی یہ ہے کہ دیگر امکانات بھی ہیں، مثال کے طور پر، مختلف کمی مختلف نتائج کا باعث بنتی ہیں۔ مثال کے طور پر درج ذیل کیوبک کثیر الجہتی کو لیں: پہلی کمی کے بعد چھت کی دوہری کا استعمال کرتے ہوئے، ہم-3 کی نچلی حد حاصل کرتے ہیں اور تین متغیرات کو تفویض کرنے کے بارے میں کوئی اشارہ نہیں دیتے ہیں۔ دوسری کمی کا استعمال کرتے ہوئے، ہم-2 کی (تنگ) نچلی حد اور ہر متغیر (جو ہے) کی زیادہ سے زیادہ تفویض حاصل کرتے ہیں۔ کثیر الجہتی کمپریشن الگورتھم ایک چھدم-بولین فنکشن کو نقشہ سازی کے طور پر غور کریں۔ پھر فرض کریں کہ ہر گتانک لازمی ہے۔ پھر ایک عدد کے لیے یہ فیصلہ کرنے کا مسئلہ P کہ آیا یہ NP سے زیادہ یا برابر ہے۔ یہ اس میں ثابت ہوتا ہے کہ کثیر الجہتی وقت میں ہم یا تو P کو حل کر سکتے ہیں یا متغیرات کی تعداد کو کم کر سکتے ہیں۔ پھر ثابت کیا کہ کثیر الجہتی وقت میں ہم یا تو P کو حل کر سکتے ہیں یا متغیرات کی تعداد کو کم کر سکتے ہیں۔ بولین فنکشن کواڈریٹک سیوڈو-بولین آپٹیمائزیشن نوٹس حوالہ جات ریاضیاتی اصلاح بھی دیکھیں۔