MAX-3LIN-EQN
ম্যাক্স-3এলআইএন-ইক্যুএন গণনামূলক জটিলতা তত্ত্বের একটি সমস্যা যেখানে ইনপুটটি রৈখিক সমীকরণের একটি পদ্ধতি (মডুলো 2)। প্রতিটি সমীকরণে সর্বাধিক 3টি চলক থাকে। সমস্যাটি হল চলকগুলির জন্য একটি অ্যাসাইনমেন্ট খুঁজে বের করা যা সর্বাধিক সংখ্যক সমীকরণকে সন্তুষ্ট করে। এই সমস্যাটি ম্যাক্স-3এসএটি সমস্যার সাথে ঘনিষ্ঠভাবে সম্পর্কিত। যে কোনও δ> 0-এর জন্য অনুপাত (1/2-δ) সহ ম্যাক্স-3এলআইএন-ইক্যুএন-এর আনুমানিক অনুমান করা এনপি-হার্ড। আরও দেখুন পিসিপি (জটিলতা) রেফারেন্স রুডিচ এবং অন্যান্য, "গণনামূলক জটিলতা তত্ত্ব", আইএএস/পার্ক সিটি গণিত সিরিজ, 2004 পৃষ্ঠা 108 জে. হস্তাদ। "কিছু সর্বোত্তম অপ্রতিরোধ্য ফলাফল"। 29তম এসিএম এস. টি. ও. সি-র কার্যধারায়, 1-10,1997 এন. পি-হার্ড সমস্যা