Karloff–Zwick algorithm
कम्प्यूटेशनल जटिलता सिद्धांत में कार्लॉफ-ज़्विक एल्गोरिथ्म, एक यादृच्छिक सन्निकटन एल्गोरिथ्म है जो इनपुट के रूप में मैक्स-3सैट बूलियन संतोषजनकता समस्या का एक उदाहरण लेता है। यदि उदाहरण संतोषजनक है, तो पाए गए कार्य का अपेक्षित भार इष्टतम का कम से कम 7/8 है। इस बात के मजबूत प्रमाण हैं (लेकिन कोई गणितीय प्रमाण नहीं) कि एल्गोरिथ्म असंतोषजनक मैक्स-3सैट उदाहरणों पर भी इष्टतम 7/8 प्राप्त करता है। हावर्ड कार्लॉफ और उरी ज्विक ने 1997 में एल्गोरिदम प्रस्तुत किया। एल्गोरिथ्म सेमीडिफाइनाइट प्रोग्रामिंग पर आधारित है। इसे समान सन्निकटन गारंटी के साथ एक नियतात्मक बहुपद-समय एल्गोरिथ्म प्राप्त करने की तकनीकों का उपयोग करके विकृत किया जा सकता है। यादृच्छिक समनुदेशन से तुलना संबंधित MAX-E3SAT समस्या के लिए, जिसमें इनपुट 3SAT सूत्र के सभी खंडों में ठीक तीन अक्षर होने की गारंटी है, सरल यादृच्छिक सन्निकटन एल्गोरिथ्म जो प्रत्येक चर को स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से एक सत्य मूल्य प्रदान करता है, अपेक्षा में सभी खंडों के 7/8 को संतुष्ट करता है, भले ही मूल सूत्र संतोषजनक हो। इसके अलावा, इस सरल एल्गोरिथ्म को सशर्त अपेक्षाओं की विधि का उपयोग करके आसानी से विकृत किया जा सकता है। हालांकि, कार्लॉफ-ज़विक एल्गोरिथ्म को इस प्रतिबंध की आवश्यकता नहीं है कि प्रत्येक खंड में इनपुट सूत्र में तीन अक्षर होने चाहिए। पी. सी. पी. प्रमेय पर पिछले काम के आधार पर, जोहान हेस्टाड ने दिखाया कि, पी. आई. सी. एन. पी. मानते हुए, मैक्स 3एस. ए. टी. के लिए कोई भी बहुपद-समय एल्गोरिथ्म 7/8 से अधिक प्रदर्शन अनुपात प्राप्त नहीं कर सकता है, भले ही समस्या के संतोषजनक उदाहरणों तक सीमित हो जिसमें प्रत्येक खंड में ठीक तीन अक्षर हों। कार्लॉफ-ज़्विक एल्गोरिथ्म और उपरोक्त सरल एल्गोरिथ्म दोनों इस मायने में इष्टतम हैं। संदर्भ सन्निकटन एल्गोरिदम यादृच्छिक एल्गोरिदम