MAX-3LIN-EQN
मैक्स-3एलआईएन-ईक्यूएन कम्प्यूटेशनल जटिलता सिद्धांत में एक समस्या है जहां इनपुट रैखिक समीकरणों (मॉड्यूलो 2) की एक प्रणाली है। प्रत्येक समीकरण में अधिकतम 3 चर होते हैं। समस्या चर के लिए एक असाइनमेंट खोजना है जो समीकरणों की अधिकतम संख्या को संतुष्ट करता है। यह समस्या मैक्स-3सैट समस्या से निकटता से संबंधित है। यह किसी भी δ> 0 के लिए अनुपात (1/2-δ) के साथ अनुमानित MAX-3LIN-EQN के लिए NP-कठिन है। पी. सी. पी. (जटिलता) संदर्भ रुडिच और अन्य, "कम्प्यूटेशनल जटिलता सिद्धांत", आई. ए. एस./पार्क सिटी गणित श्रृंखला, 2004 पृष्ठ 108 जे. हस्तद भी देखें। "कुछ इष्टतम असंगतता परिणाम"। 29वें ए. सी. एम. एस. टी. ओ. सी. की कार्यवाही में, 1-10,1997 एन. पी.-कठोर समस्याएं