MAX-3LIN-EQN
MAX-3LIN-EQN એ કોમ્પ્યુટેશનલ જટિલતા સિદ્ધાંતમાં એક સમસ્યા છે જ્યાં ઇનપુટ એ રેખીય સમીકરણોની પ્રણાલી છે (મોડ્યુલો 2). દરેક સમીકરણમાં વધુમાં વધુ 3 ચલ હોય છે. સમસ્યા એ છે કે ચલોની સોંપણી શોધવી જે સમીકરણોની મહત્તમ સંખ્યાને સંતોષે છે. આ સમસ્યા MAX-3SAT સમસ્યા સાથે નજીકથી સંબંધિત છે. તે કોઈપણ δ> 0 માટે ગુણોત્તર (1/2-δ) સાથે અંદાજે MAX-3LIN-EQN માટે NP-કઠણ છે. પી. સી. પી. (જટિલતા) સંદર્ભો રુડિચ અને અન્ય, "કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરી", આઈ. એ. એસ./પાર્ક સિટી મેથેમેટિક્સ સિરીઝ, 2004 પાનું 108 જે. હસ્તાદ પણ જુઓ. "કેટલાક શ્રેષ્ઠ અયોગ્ય પરિણામો". 29મી ACM STOCની કાર્યવાહીમાં, 1-10,1997 NP-સખત સમસ્યાઓ