Karloff–Zwick algorithm
কার্লফ-জুক অ্যালগরিদম, গণনামূলক জটিলতা তত্ত্বে, একটি র্যান্ডমাইজড আনুমানিক অ্যালগরিদম যা ইনপুট হিসাবে ম্যাক্স-3 স্যাট বুলিয়ান সন্তোষজনকতার সমস্যার একটি উদাহরণ গ্রহণ করে। যদি উদাহরণটি সন্তোষজনক হয়, তবে পাওয়া অ্যাসাইনমেন্টের প্রত্যাশিত ওজন সর্বোত্তমের কমপক্ষে 7/8 হয়। একটি শক্তিশালী প্রমাণ রয়েছে (তবে কোনও গাণিতিক প্রমাণ নেই) যে অ্যালগরিদমটি সন্তোষজনক নয় এমন ম্যাক্স-3এসএটি দৃষ্টান্তগুলিতেও সর্বোত্তম 7/8 অর্জন করে। হাওয়ার্ড কার্লফ এবং উরি জুক 1997 সালে অ্যালগরিদমটি উপস্থাপন করেন। অ্যালগরিদমটি সেমিডিফাইনাইট প্রোগ্রামিংয়ের উপর ভিত্তি করে তৈরি। এটি ব্যবহার করে বিকৃত করা যেতে পারে, উদাহরণস্বরূপ, একই আনুমানিক গ্যারান্টি সহ একটি নির্ধারক বহুপদী-সময় অ্যালগরিদম প্রদানের কৌশলগুলি। র্যান্ডম অ্যাসাইনমেন্টের সাথে তুলনা সম্পর্কিত ম্যাক্স-ই3এসএটি সমস্যার জন্য, যেখানে ইনপুট 3এসএটি সূত্রের সমস্ত ধারার ঠিক তিনটি আক্ষরিক থাকার নিশ্চয়তা দেওয়া হয়, সাধারণ র্যান্ডমাইজড আনুমানিক অ্যালগরিদম যা প্রতিটি পরিবর্তনশীলকে স্বাধীনভাবে এবং অভিন্নভাবে একটি সত্য মান বরাদ্দ করে, মূল সূত্রটি সন্তোষজনক কিনা তা নির্বিশেষে প্রত্যাশার সমস্ত ধারার 7/8 সন্তুষ্ট করে। উপরন্তু, এই সহজ অ্যালগরিদমটি শর্তাধীন প্রত্যাশার পদ্ধতি ব্যবহার করে সহজেই বিকৃত করা যেতে পারে। কার্লফ-জউইক অ্যালগরিদমের জন্য অবশ্য এই সীমাবদ্ধতার প্রয়োজন নেই যে ইনপুট সূত্রের প্রতিটি ধারায় তিনটি আক্ষরিক অক্ষর থাকা উচিত। অনুকূলতা পি. সি. পি উপপাদ্যের উপর পূর্ববর্তী কাজের উপর ভিত্তি করে, জোহান হ্যাস্টাদ দেখিয়েছেন যে, পি. আই. ভি. এন. পি ধরে নিলে, ম্যাক্স 3এস. এ. টি-র জন্য কোনও পলিনোমিয়াল-টাইম অ্যালগরিদম 7/8-এর বেশি কর্মক্ষমতা অনুপাত অর্জন করতে পারে না, এমনকি সমস্যার সন্তোষজনক দৃষ্টান্তের মধ্যে সীমাবদ্ধ থাকলেও যেখানে প্রতিটি ধারায় ঠিক তিনটি আক্ষরিক রয়েছে। কার্লফ-জুক অ্যালগরিদম এবং উপরের সহজ অ্যালগরিদম উভয়ই এই অর্থে সর্বোত্তম। রেফারেন্স আনুমানিক অ্যালগরিদম এলোমেলো অ্যালগরিদম