Karloff–Zwick algorithm
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, કાર્લોફ-ઝ્વિક અલ્ગોરિધમ એક રેન્ડમાઇઝ્ડ એપ્રોક્સીમેશન અલ્ગોરિધમ છે, જે ઇનપુટ તરીકે MAX-3SAT બુલિયન સંતોષકારક સમસ્યાનું ઉદાહરણ લે છે. જો ઉદાહરણ સંતોષકારક હોય, તો મળેલા સોંપણીનું અપેક્ષિત વજન ઓછામાં ઓછું 7/8 શ્રેષ્ઠ છે. ત્યાં મજબૂત પુરાવા છે (પરંતુ ગાણિતિક પુરાવા નથી) કે અલ્ગોરિધમ અસંતોષકારક MAX-3SAT ઉદાહરણો પર પણ શ્રેષ્ઠ 7/8 પ્રાપ્ત કરે છે. હોવર્ડ કાર્લોફ અને ઉરી ઝવિકે 1997માં અલ્ગોરિધમ રજૂ કર્યું હતું. અલ્ગોરિધમ અર્ધ-મર્યાદિત પ્રોગ્રામિંગ પર આધારિત છે. દાખલા તરીકે, સમાન અંદાજની બાંયધરીઓ સાથે નિર્ધારક બહુપદી-સમય અલ્ગોરિધમ મેળવવાની તકનીકોનો ઉપયોગ કરીને તેને વિકૃત કરી શકાય છે. રેન્ડમ સોંપણી સાથે સરખામણી સંબંધિત MAX-E3SAT સમસ્યા માટે, જેમાં ઇનપુટ 3SAT સૂત્રની તમામ કલમો બરાબર ત્રણ શાબ્દિક હોવાની બાંયધરી આપે છે, સરળ રેન્ડમાઇઝ્ડ એપ્રોક્સીમેશન અલ્ગોરિધમ જે દરેક ચલને સ્વતંત્ર રીતે અને એકસરખી રીતે રેન્ડમ રીતે સત્ય મૂલ્ય સોંપે છે તે અપેક્ષાએ તમામ કલમોમાંથી 7/8 ને સંતોષે છે, પછી ભલે તે મૂળ સૂત્ર સંતોષકારક હોય. વધુમાં, શરતી અપેક્ષાઓની પદ્ધતિનો ઉપયોગ કરીને આ સરળ અલ્ગોરિધમનો સરળતાથી દૂર કરી શકાય છે. જોકે, કાર્લોફ-ઝ્વિક અલ્ગોરિધમને એ પ્રતિબંધની જરૂર નથી કે ઇનપુટ સૂત્રમાં દરેક કલમમાં ત્રણ અક્ષરો હોવા જોઈએ. પી. સી. પી. થીયરમ પરના અગાઉના કાર્યને આધારે, જોહાન હાસ્ટાડે દર્શાવ્યું હતું કે, એમ ધારીને કે પી ≤ એન. પી., એમ. એ. એક્સ. 3એસ. એ. ટી. માટે કોઈ બહુપદી-સમય અલ્ગોરિધમ 7/8 થી વધુ પ્રદર્શન ગુણોત્તર પ્રાપ્ત કરી શકશે નહીં, ભલે તે સમસ્યાના સંતોષકારક ઉદાહરણો સુધી મર્યાદિત હોય જેમાં દરેક કલમ બરાબર ત્રણ અક્ષરો ધરાવે છે. તેથી કાર્લોફ-ઝ્વિક અલ્ગોરિધમ અને ઉપરોક્ત સરળ અલ્ગોરિધમ બંને આ અર્થમાં શ્રેષ્ઠ છે. સંદર્ભો અંદાજિત અલ્ગોરિધમ્સ રેન્ડમાઇઝ્ડ અલ્ગોરિધમ્સ