Karloff–Zwick algorithm
ಕಾರ್ಲೊಫ್-ಝ್ವಿಕ್ ಅಲ್ಗಾರಿದಮ್, ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, MAX-3SAT ಬೂಲಿಯನ್ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಯನ್ನು ಇನ್ಪುಟ್ ಆಗಿ ತೆಗೆದುಕೊಳ್ಳುವ ಯಾದೃಚ್ಛಿಕ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ನಿದರ್ಶನವು ತೃಪ್ತಿಕರವಾಗಿದ್ದರೆ, ಕಂಡುಬರುವ ನಿಯೋಜನೆಯ ನಿರೀಕ್ಷಿತ ತೂಕವು ಕನಿಷ್ಠ 7/8 ಆಗಿದೆ. ಅತೃಪ್ತಿಕರವಾದ MAX-3SAT ನಿದರ್ಶನಗಳಲ್ಲಿಯೂ ಸಹ ಅಲ್ಗಾರಿದಮ್ ಅತ್ಯುತ್ತಮವಾದ 7/8 ಅನ್ನು ಸಾಧಿಸುತ್ತದೆ ಎಂಬುದಕ್ಕೆ ಬಲವಾದ ಪುರಾವೆಗಳಿವೆ (ಆದರೆ ಗಣಿತದ ಪುರಾವೆಗಳಿಲ್ಲ). ಹೊವಾರ್ಡ್ ಕಾರ್ಲೋಫ್ ಮತ್ತು ಉರಿ ಝ್ವಿಕ್ 1997 ರಲ್ಲಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಿದರು. ಅಲ್ಗಾರಿದಮ್ ಸೆಮಿಡಿಫೈನೈಟ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅನ್ನು ಆಧರಿಸಿದೆ. ಉದಾಹರಣೆಗೆ, ಅದೇ ಅಂದಾಜು ಖಾತರಿಗಳೊಂದಿಗೆ ನಿರ್ಣಾಯಕ ಬಹುಪದ-ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೀಡುವ ತಂತ್ರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಇದನ್ನು ವಿಕೇಂದ್ರೀಕರಿಸಬಹುದು. ಯಾದೃಚ್ಛಿಕ ನಿಯೋಜನೆಗೆ ಹೋಲಿಕೆ ಸಂಬಂಧಿತ MAX-E3SAT ಸಮಸ್ಯೆಗಾಗಿ, ಇದರಲ್ಲಿ ಇನ್ಪುಟ್ 3SAT ಸೂತ್ರದಲ್ಲಿನ ಎಲ್ಲಾ ಷರತ್ತುಗಳು ನಿಖರವಾಗಿ ಮೂರು ಅಕ್ಷರಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ ಎಂದು ಖಾತರಿಪಡಿಸಲಾಗಿದೆ, ಸರಳ ಯಾದೃಚ್ಛಿಕ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಪ್ರತಿ ವೇರಿಯೇಬಲ್ಗೆ ಸ್ವತಂತ್ರವಾಗಿ ಮತ್ತು ಏಕರೂಪವಾಗಿ ಯಾದೃಚ್ಛಿಕವಾಗಿ ಸತ್ಯ ಮೌಲ್ಯವನ್ನು ನಿಗದಿಪಡಿಸುತ್ತದೆ, ಮೂಲ ಸೂತ್ರವು ತೃಪ್ತಿಕರವಾಗಿದೆಯೇ ಎಂಬುದನ್ನು ಲೆಕ್ಕಿಸದೆ ನಿರೀಕ್ಷೆಯಲ್ಲಿರುವ ಎಲ್ಲಾ ಷರತ್ತುಗಳ 7/8 ಅನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ. ಇದಲ್ಲದೆ, ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಗಳ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಈ ಸರಳ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸುಲಭವಾಗಿ ಬೇರ್ಪಡಿಸಬಹುದು. ಆದಾಗ್ಯೂ, ಕಾರ್ಲೋಫ್-ಝ್ವಿಕ್ ಅಲ್ಗಾರಿದಮ್ಗೆ, ಇನ್ಪುಟ್ ಸೂತ್ರವು ಪ್ರತಿ ಷರತ್ತಿನಲ್ಲಿ ಮೂರು ಅಕ್ಷರಗಳನ್ನು ಹೊಂದಿರಬೇಕು ಎಂಬ ನಿರ್ಬಂಧದ ಅಗತ್ಯವಿಲ್ಲ. ಪಿ. ಸಿ. ಪಿ. ಪ್ರಮೇಯದ ಮೇಲಿನ ಹಿಂದಿನ ಸಂಶೋಧನೆಯ ಆಧಾರದ ಮೇಲೆ, ಮ್ಯಾಕ್ಸ್ 3ಎಸ್ಎಟಿಗಾಗಿ ಯಾವುದೇ ಬಹುಪದ-ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ 7/8 ಅನ್ನು ಮೀರಿದ ಕಾರ್ಯಕ್ಷಮತೆಯ ಅನುಪಾತವನ್ನು ಸಾಧಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ ಎಂದು ಜೋಹಾನ್ ಹಾಸ್ಟಾಡ್ ತೋರಿಸಿದರು, ಪ್ರತಿ ಷರತ್ತು ನಿಖರವಾಗಿ ಮೂರು ಅಕ್ಷರಗಳನ್ನು ಹೊಂದಿರುವ ಸಮಸ್ಯೆಯ ತೃಪ್ತಿಕರ ನಿದರ್ಶನಗಳಿಗೆ ಸೀಮಿತವಾಗಿದ್ದರೂ ಸಹ. ಆದ್ದರಿಂದ ಕಾರ್ಲೋಫ್-ಝ್ವಿಕ್ ಅಲ್ಗಾರಿದಮ್ ಮತ್ತು ಮೇಲಿನ ಸರಳ ಅಲ್ಗಾರಿದಮ್ ಎರಡೂ ಈ ಅರ್ಥದಲ್ಲಿ ಸೂಕ್ತವಾಗಿವೆ. ಉಲ್ಲೇಖಗಳು ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳು ಯಾದೃಚ್ಛಿಕ ಕ್ರಮಾವಳಿಗಳು