MAX-3LIN-EQN
MAX-3LIN-EQN ಎಂಬುದು ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಒಂದು ಸಮಸ್ಯೆಯಾಗಿದ್ದು, ಅಲ್ಲಿ ಇನ್ಪುಟ್ ರೇಖೀಯ ಸಮೀಕರಣಗಳ (ಮಾಡ್ಯುಲೋ 2) ವ್ಯವಸ್ಥೆಯಾಗಿದೆ. ಪ್ರತಿ ಸಮೀಕರಣವು ಗರಿಷ್ಠ 3 ಅಸ್ಥಿರಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಸಮೀಕರಣಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ಅಸ್ಥಿರಗಳಿಗೆ ನಿಯೋಜನೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಸಮಸ್ಯೆಯಾಗಿದೆ. ಈ ಸಮಸ್ಯೆಯು MAX-3SAT ಸಮಸ್ಯೆಯೊಂದಿಗೆ ನಿಕಟ ಸಂಬಂಧ ಹೊಂದಿದೆ. ಯಾವುದೇ δ> 0 ಗೆ (1/2-δ) ಅನುಪಾತದೊಂದಿಗೆ MAX-3LIN-EQN ಅನ್ನು ಅಂದಾಜು ಮಾಡಲು NP-ಕಠಿಣವಾಗಿದೆ. ಪಿಸಿಪಿ (ಸಂಕೀರ್ಣತೆ) ಉಲ್ಲೇಖಗಳು ರುಡಿಚ್ ಮತ್ತು ಇತರರು, "ಕಂಪ್ಯೂಟೇಶನಲ್ ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಥಿಯರಿ", ಐಎಎಸ್/ಪಾರ್ಕ್ ಸಿಟಿ ಮ್ಯಾಥಮ್ಯಾಟಿಕ್ಸ್ ಸೀರೀಸ್, 2004 ಪುಟ 108 ಜೆ. ಹಸ್ತದ್ ಅನ್ನು ಸಹ ನೋಡಿ. "ಕೆಲವು ಅತ್ಯುತ್ತಮ ಅಸಮರ್ಪಕ ಫಲಿತಾಂಶಗಳು". 29ನೇ ಎಸಿಎಂ ಎಸ್ಟಿಒಸಿ, 1-10,1997ರ ಎನ್ಪಿ-ಹಾರ್ಡ್ ಸಮಸ್ಯೆಗಳ ವಿಚಾರಣೆಯಲ್ಲಿ