यादृच्छिक संतोषजनक समस्याओं में समाधान छुपाना: एक सांख्यिकी यांत्रिकी दृष्टिकोण

NP-कम्प्लीट समस्याओं के लिए यादृच्छिक स्थानीय खोज एल्गोरिदम का मूल्यांकन करने में एक प्रमुख समस्या यह है कि हमें ऐसे कठिन परीक्षण उदाहरणों की व्यवस्थित पीढ़ी की आवश्यकता है जिनके संबंध में अनुकूल समाधान की पहले से ज्ञात विशेषताएं हों। सांख्यिकी यांत्रिकी परिणामों के आधार पर, हम 3-संतोषजनक समस्या के लिए कठिन और संतोषजनक उदाहरणों के यादृच्छिक जनरेटर का प्रस्ताव करते हैं। कठिनतम समस्या उदाहरणों की डिज़ाइन एक प्रथम श्रेणी के फेरोमैग्नेटिक चरण संक्रमण और उत्साहित राज्यों की कांचीय प्रकृति के अस्तित्व पर आधारित है। विश्लेषणात्मक भविष्यवाणियाँ पूर्ण और यादृच्छिक स्थानीय एल्गोरिदम से प्राप्त संख्यात्मक परिणामों द्वारा पुष्टि की जाती हैं।