Karloff–Zwick algorithm
کارلوف زوک الگورتھم، کمپیوٹیشنل پیچیدگی کے نظریہ میں، ایک بے ترتیب تخمینہ الگورتھم ہے جو ان پٹ کے طور پر میکس-3 ایس اے ٹی بولین اطمینان بخش مسئلے کی مثال لیتا ہے۔ اگر مثال تسلی بخش ہے، تو پائے جانے والے اسائنمنٹ کا متوقع وزن کم از کم 7/8 زیادہ سے زیادہ ہے۔ مضبوط ثبوت موجود ہیں (لیکن ریاضیاتی ثبوت نہیں) کہ الگورتھم غیر تسلی بخش میکس-3 ایس اے ٹی مثالوں پر بھی 7/8 زیادہ سے زیادہ حاصل کرتا ہے۔ ہاورڈ کارلوف اور اوری زوک نے 1997 میں الگورتھم پیش کیا۔ الگورتھم سیمی ڈفائنٹ پروگرامنگ پر مبنی ہے۔ اسی اندازے کی ضمانتوں کے ساتھ ایک تعیناتی کثیر الجہتی وقت الگورتھم حاصل کرنے کی تکنیکوں کا استعمال کرتے ہوئے، مثال کے طور پر، اسے بے ترتیب کیا جا سکتا ہے۔ بے ترتیب تفویض سے موازنہ متعلقہ MAX-E3SAT مسئلے کے لیے، جس میں ان پٹ 3SAT فارمولے کی تمام شقوں کو بالکل تین لفظی ہونے کی ضمانت دی جاتی ہے، سادہ بے ترتیب تخمینہ الگورتھم جو ہر متغیر کو آزادانہ طور پر اور یکساں طور پر بے ترتیب طور پر سچائی کی قیمت تفویض کرتا ہے، توقع میں تمام شقوں میں سے 7/8 کو مطمئن کرتا ہے، اس سے قطع نظر کہ اصل فارمولا تسلی بخش ہے۔ مزید برآں، اس سادہ الگورتھم کو مشروط توقعات کے طریقہ کار کا استعمال کرتے ہوئے آسانی سے الگ کیا جا سکتا ہے۔ کارلوف زوک الگورتھم، تاہم، اس پابندی کی ضرورت نہیں ہے کہ ان پٹ فارمولے میں ہر شق میں تین حرف ہونے چاہئیں۔ پی سی پی تھیوریم پر پچھلے کام کی بنیاد پر، جوہان ہاسٹیڈ نے دکھایا کہ، پی ष्णپ فرض کرتے ہوئے، میکس 3 ایس اے ٹی کے لیے کوئی کثیر الجہتی وقت کا الگورتھم 7/8 سے زیادہ کارکردگی کا تناسب حاصل نہیں کر سکتا، یہاں تک کہ جب اس مسئلے کی تسلی بخش مثالوں تک محدود ہو جس میں ہر شق بالکل تین لفظی پر مشتمل ہو۔ کارلوف زوک الگورتھم اور مذکورہ بالا سادہ الگورتھم دونوں اس لحاظ سے بہترین ہیں۔ حوالہ جات تخمینہ الگورتھم بے ترتیب الگورتھم