Graver basis
ಅನ್ವಯಿಕ ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ಗ್ರೇವರ್ ಬೇಸ್ಗಳು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ರೇಖೀಯ ಮತ್ತು ವಿವಿಧ ರೇಖಾತ್ಮಕವಲ್ಲದ ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳ ಪುನರಾವರ್ತಿತ ಪರಿಹಾರಗಳನ್ನು ಸಕ್ರಿಯಗೊಳಿಸುತ್ತವೆ. ಅವುಗಳನ್ನು ಜ್ಯಾಕ್ ಇ. ಗ್ರೇವರ್ ಪರಿಚಯಿಸಿದರು. ಗ್ರೋಬ್ನರ್ ಬೇಸ್ಗಳ ಸಿದ್ಧಾಂತದೊಂದಿಗಿನ ಅವರ ಸಂಬಂಧವನ್ನು ಬರ್ನ್ಡ್ ಸ್ಟರ್ಮ್ಫೆಲ್ಸ್ ಚರ್ಚಿಸಿದ್ದಾರೆ. ಗ್ರೇವರ್ ಬೇಸ್ಗಳ ಅಲ್ಗಾರಿದಮಿಕ್ ಸಿದ್ಧಾಂತ ಮತ್ತು ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ಗೆ ಅದರ ಅನ್ವಯವನ್ನು ಷ್ಮುಯೆಲ್ ಒನ್ ವಿವರಿಸಿದ್ದಾರೆ. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನ m × n ಪೂರ್ಣಾಂಕದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಗ್ರೇವರ್ ಆಧಾರವು ಯಾವಾಗ ಮತ್ತು ಎಲ್ಲಾ i ಗಾಗಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಉತ್ತಮ ಭಾಗಶಃ ಕ್ರಮದ ಅಡಿಯಲ್ಲಿ ಸೆಟ್ನಲ್ಲಿ ಕನಿಷ್ಠ ಅಂಶಗಳ ಸೀಮಿತ ಗುಂಪಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ಗ್ರೇವರ್ ಆಧಾರವು ವಾಹಕಗಳು (2,-1,0), (0,-1,2), (1,0,-1), (1,-1,1) ಮತ್ತು ಅವುಗಳ ನಿರಾಕರಣೆಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಗ್ರೇವರ್ ಬೇಸ್ಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅನ್ನು ಪರಿಹರಿಸುವುದು ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಎಂಬುದು ರೇಖೀಯ ಅಸಮಾನತೆಗಳ ವ್ಯವಸ್ಥೆಯನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ಪೂರ್ಣಾಂಕ ಬಿಂದುಗಳ ಗುಂಪಿನ ಮೇಲೆ ರೇಖೀಯ ಅಥವಾ ರೇಖಾತ್ಮಕವಲ್ಲದ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯವನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿಸುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಔಪಚಾರಿಕವಾಗಿ, ಇದನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಪ್ರಮಾಣಿತ ರೂಪದಲ್ಲಿ ಬರೆಯಬಹುದುಃ ಇದು ಅತ್ಯಂತ ಮೂಲಭೂತ ಪ್ರತ್ಯೇಕ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ ಮತ್ತು ವಿವಿಧ ಕ್ಷೇತ್ರಗಳಲ್ಲಿ ಬಹಳ ವಿಶಾಲವಾದ ಮಾಡೆಲಿಂಗ್ ಶಕ್ತಿ ಮತ್ತು ಹಲವಾರು ಅನ್ವಯಿಕೆಗಳನ್ನು ಹೊಂದಿದೆ, ಆದರೆ ಕೆಳಗೆ ತಿಳಿಸಿದಂತೆ ಗಣನೆಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಇದು ತುಂಬಾ ಕಠಿಣವಾಗಿದೆ. ಆದಾಗ್ಯೂ, ಗ್ರೇವರ್ ಆಧಾರದ ಮೇಲೆ, ರೇಖೀಯ ಮತ್ತು ವಿವಿಧ ರೇಖಾತ್ಮಕವಲ್ಲದ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯಗಳೊಂದಿಗಿನ ಸಮಸ್ಯೆಯನ್ನು ಮುಂದೆ ವಿವರಿಸಿದಂತೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಲೀನಿಯರ್ ಇಂಟಿಜರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅತ್ಯಂತ ಹೆಚ್ಚು ಅಧ್ಯಯನ ಮಾಡಲಾದ ಪ್ರಕರಣವು ಲೀನಿಯರ್ ಇಂಟಿಜರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಆಗಿದೆ, ಎಲ್ಲಾ ಅಸ್ಥಿರಗಳು ಕೆಳಗಿನಿಂದ ಮತ್ತು ಮೇಲಿನಿಂದ ಬಂಧಿಸಲ್ಪಟ್ಟಿವೆ ಎಂದು ಭಾವಿಸಬಹುದುಃ ಅಂತಹ ಮಿತಿಗಳು ಕೈಯಲ್ಲಿರುವ ಅಪ್ಲಿಕೇಶನ್ನಲ್ಲಿ ನೈಸರ್ಗಿಕವಾಗಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತವೆ, ಅಥವಾ ಯಾವುದೇ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರಗಳನ್ನು ಕಳೆದುಕೊಳ್ಳದೆ ಜಾರಿಗೊಳಿಸಬಹುದು. ಆದರೆ, ರೇಖೀಯ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯಗಳೊಂದಿಗೂ ಸಹ ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಬಹುಶಃ ಪರಿಹರಿಸಲಾಗುವುದಿಲ್ಲ. ಆದಾಗ್ಯೂ, ಗ್ರೇವರ್ ಆಧಾರವು ಈ ಕೆಳಗಿನ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿದೆ. ಪ್ರತಿಯೊಂದು ಕಾರ್ಯಸಾಧ್ಯವಾದ ಬಿಂದುವಿಗೆ x: ಒಂದೋ x ಸೂಕ್ತವಾಗಿರುತ್ತದೆ (ಅಂದರೆ, ನಿರ್ಬಂಧಗಳನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತದೆ); ಅಥವಾ x + g ಕಾರ್ಯಸಾಧ್ಯವಾಗುವಂತೆ ವೆಕ್ಟರ್ g ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ ಮತ್ತು (ಅಂದರೆ, x ಅನ್ನು ಗ್ರೇವರ್ ಆಧಾರದ ಅಂಶವನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಸುಧಾರಿಸಬಹುದು). ಆದ್ದರಿಂದ, ಗ್ರೇವರ್ ಆಧಾರದ ಮೇಲೆ, ಐಎಲ್ಪಿಯನ್ನು ಈ ಕೆಳಗಿನ ಸರಳ ಪುನರಾವರ್ತಿತ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಕೆಲವು ಆರಂಭಿಕ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಬಿಂದು x ಅನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಮೊದಲು ಭಾವಿಸಿ. ಸಾಧ್ಯವಿದ್ದರೂ, ಈ ಕೆಳಗಿನ ಪುನರಾವರ್ತನೆಯನ್ನು ಪುನರಾವರ್ತಿಸಿಃ ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕ q ಮತ್ತು ಅಂಶ g ಅನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ, ಅದು x + qg ಮಿತಿಯನ್ನು ಉಲ್ಲಂಘಿಸುವುದಿಲ್ಲ ಮತ್ತು ಸಾಧ್ಯವಾದಷ್ಟು ಉತ್ತಮ ಸುಧಾರಣೆಯನ್ನು ನೀಡುತ್ತದೆ; x: = x + qg ಅನ್ನು ನವೀಕರಿಸಿ ಮತ್ತು ಮುಂದಿನ ಪುನರಾವರ್ತನೆಗೆ ಮುಂದುವರಿಯಿರಿ. ಕೊನೆಯ ಬಿಂದು x ಸೂಕ್ತವಾಗಿದೆ ಮತ್ತು ಪುನರಾವರ್ತನೆಗಳ ಸಂಖ್ಯೆಯು ಬಹುಪದವಾಗಿದೆ. ಆರಂಭಿಕ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಲು, ಸೂಕ್ತವಾದ ಸಹಾಯಕ ಕಾರ್ಯಕ್ರಮವನ್ನು ಸ್ಥಾಪಿಸಬಹುದು ಮತ್ತು ಅದೇ ರೀತಿಯಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಸಾಮಾನ್ಯ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯಗಳ ವಿಷಯಕ್ಕೆ ತಿರುಗಿ, ಚರರಾಶಿಗಳು ಮಿತಿಯಿಲ್ಲದವರಾಗಿದ್ದರೆ, ಸಮಸ್ಯೆಯು ವಾಸ್ತವವಾಗಿ ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳಲಾಗುವುದಿಲ್ಲಃ ಇದು ಹಿಲ್ಬರ್ಟ್ನ 10ನೇ ಸಮಸ್ಯೆಯ ಪರಿಹಾರದಿಂದ ಅನುಸರಿಸುತ್ತದೆ (ನೋಡಿ), ಯಾವುದೇ ಅಲ್ಗಾರಿದಮ್ ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲ, ಇದು 58 ಚರರಾಶಿಗಳಲ್ಲಿ ಡಿಗ್ರಿ 8 ರ ಪೂರ್ಣಾಂಕ ಬಹುಪದ f ಅನ್ನು ನೀಡಿದರೆ, ಎಲ್ಲಾ 58-ಆಯಾಮದ ಪೂರ್ಣಾಂಕ ವಾಹಕಗಳ ಮೇಲೆ f ನ ಕನಿಷ್ಠ ಮೌಲ್ಯವು 0 ಆಗಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಅಸ್ಥಿರಗಳನ್ನು ಬಂಧಿಸಿದಾಗ, ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಒಳಗೊಂಡಂತೆ ಹಲವಾರು ರೇಖಾತ್ಮಕವಲ್ಲದ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯಗಳಿಗೆ ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಗ್ರೇವರ್ ಆಧಾರವನ್ನು ಬಳಸಿಕೊಂಡು ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಬಹುದುಃ ರೂಪದ ಬೇರ್ಪಡಿಸಬಹುದಾದ-ಕನ್ವೆಕ್ಸ್ ಕಾರ್ಯಗಳು; ನಿರ್ದಿಷ್ಟವಾಗಿ ಪ್ರತಿ ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕ p ಗೆ p-ನಾರ್ಮ್; ಕಾಂಪೋಸಿಟ್-ಕಾನ್ಕೇವ್ ಕಾರ್ಯಗಳು f (x) = g (Wx), ಇಲ್ಲಿ W ಎಂಬುದು d ಸ್ಥಿರವಾದ d × n ಪೂರ್ಣಾಂಕ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿದೆ, ಮತ್ತು ಅಲ್ಲಿ g ಎಂಬುದು d-ವೇರಿಯೇಟ್ ಕಾನ್ಕೇವ್ ಕಾರ್ಯವಾಗಿದೆ; ಕೆಲವು (in)-ನಿಶ್ಚಿತ ಚತುರ್ಭುಜ ಮತ್ತು ಉನ್ನತ ಮಟ್ಟದ ಬಹುಪದೀಯ ಕಾರ್ಯಗಳು. ಕೆಲವು ಅನ್ವಯಿಕೆಗಳು ಬಹು-ಆಯಾಮದ ಕೋಷ್ಟಕಗಳು ಮೂರು-ಆಯಾಮದ ಕೋಷ್ಟಕಗಳ ಮೇಲೆ ಈ ಕೆಳಗಿನ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಗಣಿಸಿ, ಋಣಾತ್ಮಕವಲ್ಲದ ಪೂರ್ಣಾಂಕಗಳೊಂದಿಗೆ (ಇದರ ಗರಿಷ್ಠ ಮೌಲ್ಯವು ಮೇಲಿನಿಂದ ಎಲ್ಲಾ ಅಸ್ಥಿರಗಳನ್ನು ಸೂಚ್ಯವಾಗಿ ಬಂಧಿಸುತ್ತದೆ). ಈ ವ್ಯವಸ್ಥೆಯ ವ್ಯಾಖ್ಯಾನಿಸುವ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು (lm + ln + mn) × (lmn) ನಿಂದ ಸೂಚಿಸಿ. ಈ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಸಾಮಾನ್ಯವಾಗಿ ಸಂಪೂರ್ಣವಾಗಿ ಏಕರೂಪವಾಗಿಲ್ಲ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಆದಾಗ್ಯೂ, ಪ್ರತಿ ಸ್ಥಿರ l ಮತ್ತು m ಗೆ, ಅದರ ಗ್ರೇವರ್ ಆಧಾರವನ್ನು n ನಲ್ಲಿ ಬಹುಪದವಾಗಿರುವ ಸಮಯದಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ಮೇಲೆ ತಿಳಿಸಲಾದ ಫಲಿತಾಂಶಗಳು ಈ ಸಮಸ್ಯೆಯನ್ನು ಸ್ಥಿರ l ಮತ್ತು m ಮತ್ತು ಚರ n ಗೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಕೋಷ್ಟಕದ ಒಂದು ಬದಿ l ಅನ್ನು ಮಾತ್ರ ಸ್ಥಿರಗೊಳಿಸಿದರೆ (l = 3 ರೊಂದಿಗೆ ಸಹ) m ಮತ್ತು n ಎರಡೂ ಬದಲಾಗುತ್ತಿರುವಾಗ, ಸಮಸ್ಯೆಯು NP ಗಟ್ಟಿಯಾಗಿರುತ್ತದೆ, ಇದರಲ್ಲಿ ತೋರಿಸಿರುವಂತೆ. ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, ಉನ್ನತ-ಆಯಾಮದ ಕೋಷ್ಟಕದ ಸಮಸ್ಯೆಗಳಿಗೆ ಇದೇ ರೀತಿಯ ಧನಾತ್ಮಕ ಫಲಿತಾಂಶಗಳು ಇರುತ್ತವೆ (ಇದರಲ್ಲಿ ಪರಿಚಯಿಸಲಾಗಿದೆ): ಪ್ರತಿ ಸ್ಥಿರ ಡಿ ಮತ್ತು, (ಅಲ್ಲದ)-ರೇಖಾತ್ಮಕ ಆಪ್ಟಿಮೈಸೇಶನ್ ಅನ್ನು ಅಸ್ಥಿರ n ಮತ್ತು ನಿಗದಿತ ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ಕೋಷ್ಟಕಗಳ ಮೇಲೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಮಾಡಬಹುದು. ಸಂಖ್ಯಾಶಾಸ್ತ್ರೀಯ ದತ್ತಸಂಚಯಗಳಲ್ಲಿ ಭದ್ರತಾ ಸಮಸ್ಯೆಗಳು ಮತ್ತು ಗೌಪ್ಯತೆಯನ್ನು ಪ್ರವೇಶಿಸಲು ಇದು ಮತ್ತಷ್ಟು ಅನ್ವಯಗಳನ್ನು ಹೊಂದಿದೆ. ಬಹು-ಸರಕು ಹರಿವುಗಳು ಪೂರೈಕೆ, ಬಳಕೆ ಮತ್ತು ಸಾಮರ್ಥ್ಯದ ನಿರ್ಬಂಧಗಳಿಗೆ ಒಳಪಟ್ಟು m ಪೂರೈಕೆದಾರರಿಂದ n ಗ್ರಾಹಕರಿಗೆ k ವಿಧದ ಪೂರ್ಣಾಂಕ ಸರಕುಗಳನ್ನು ರವಾನಿಸುವ ಪೂರ್ಣಾಂಕ ಬಹು-ಸರಕು ಹರಿವಿನ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಗಣಿಸಿ, ಇದರಿಂದಾಗಿ ರೇಖಾತ್ಮಕ ಅಥವಾ ದಟ್ಟಣೆ-ಅವಲಂಬಿತ ಕನ್ವೆಕ್ಸ್ ವೆಚ್ಚಗಳ ಮೊತ್ತವನ್ನು ಕಡಿಮೆ ಮಾಡಬಹುದು. ನಂತರ ಪ್ರತಿ ಸ್ಥಿರ k ಮತ್ತು m ಗೆ, ವ್ಯಾಖ್ಯಾನಿಸುವ ವ್ಯವಸ್ಥೆಯ ಗ್ರೇವರ್ ಆಧಾರವನ್ನು ಲೆಕ್ಕ ಹಾಕಬಹುದು ಮತ್ತು ಪರಿಣಾಮವಾಗಿ ಬೇರ್ಪಡಿಸಬಹುದಾದ-ಕನ್ವೆಕ್ಸ್ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯವನ್ನು ಸಮಯಕ್ಕೆ ಕಡಿಮೆ ಮಾಡಬಹುದು, ಇದು ಗ್ರಾಹಕರ ಚರ ಸಂಖ್ಯೆ n ಮತ್ತು ಉಳಿದ ದತ್ತಾಂಶದಲ್ಲಿ ಬಹುಪದವಾಗಿದೆ. ಗ್ರೇವರ್ ಬೇಸ್ಗಳ ಅಲ್ಗಾರಿದಮಿಕ್ ಸಿದ್ಧಾಂತದ ಅನೇಕ ಅನ್ವಯಿಕೆಗಳು ಸೇರಿವೆಃ ಯಾದೃಚ್ಛಿಕ ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್, ಎನ್-ಪಟ್ಟು ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್, ಎನ್-ಪಟ್ಟು 4-ಬ್ಲಾಕ್ ವಿಭಜನೆ ಮಾಡಬಹುದಾದ ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್, ಕ್ಲಸ್ಟರಿಂಗ್, ಸಂಖ್ಯಾಶಾಸ್ತ್ರೀಯ ದತ್ತಸಂಚಯಗಳಲ್ಲಿ ಬಹಿರಂಗಪಡಿಸುವಿಕೆ ನಿಯಂತ್ರಣ ಮತ್ತು ಅವಿಭಾಜ್ಯ ವಸ್ತುಗಳ ನ್ಯಾಯಯುತ ಹಂಚಿಕೆ. ಈ ಕೆಲವು ಅನ್ವಯಿಕೆಗಳಲ್ಲಿ ಸಂಬಂಧಿತ ಗ್ರೇವರ್ ಆಧಾರವನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಲೆಕ್ಕಹಾಕಲು ಸಾಧ್ಯವಿಲ್ಲ, ಆದರೆ ಅದನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಬಳಸಲು ಅನುವು ಮಾಡಿಕೊಡುವ ಪರೋಕ್ಷ ರೀತಿಯಲ್ಲಿ ಪ್ರವೇಶಿಸಬಹುದು. ಸಾರ್ವತ್ರಿಕತೆ ಮತ್ತು ನಿಯತಾಂಕಮಾಪನ ಪ್ರತಿ (ಸೀಮಿತ) ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯು ಕೆಲವು m ಮತ್ತು n ಮತ್ತು ಕೆಲವು ಸಾಲಿನ ಮೊತ್ತಗಳಿಗೆ ಮೇಲೆ ಚರ್ಚಿಸಲಾದ 3 × m × n ಟೇಬಲ್ ಸಮಸ್ಯೆಗೆ ನಿಖರವಾಗಿ ಸಮನಾಗಿರುತ್ತದೆ ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ಹೀಗಾಗಿ, ಅಂತಹ 3 × m × n ಟೇಬಲ್ ಸಮಸ್ಯೆಗಳು ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ಗೆ ಸಾರ್ವತ್ರಿಕವಾಗಿವೆ. ಇದಲ್ಲದೆ, ಪ್ರತಿ ಸ್ಥಿರ m ಗೆ, ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಂಗಳ ಪರಿಣಾಮವಾಗಿ ಬರುವ ವರ್ಗವನ್ನು ಮೇಲೆ ವಿವರಿಸಿದ ಪುನರಾವರ್ತಿತ ಗ್ರೇವರ್ ಆಧಾರ ವಿಧಾನದಿಂದ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಆದ್ದರಿಂದ ಕೋಷ್ಟಕದ ಅಗಲ m ಎಲ್ಲಾ ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳ ನಿಯತಾಂಕವನ್ನು ಒದಗಿಸುತ್ತದೆ. ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ಗಾಗಿ ಅಂದಾಜುಗಳ ಶ್ರೇಣಿವ್ಯವಸ್ಥೆಯು ಮೇಲೆ ಚರ್ಚಿಸಲಾದ ಸಾರ್ವತ್ರಿಕ 3 × m × n ಕೋಷ್ಟಕ ಸಮಸ್ಯೆಯನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುವ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಗ್ರೇವರ್ ಆಧಾರದಿಂದ ಸೂಚಿಸುತ್ತದೆ. ಎಲ್ಲಾ ರೇಖೆಗಳ ಮೊತ್ತವು 0 ಕ್ಕೆ ಸಮನಾಗಿರುವ 3 × m × n ಕೋಷ್ಟಕಗಳು ಇದರ ಅಂಶಗಳಾಗಿವೆ. ಅಂತಹ ಕೋಷ್ಟಕದ ಪ್ರಕಾರವು ಅದರ ಶೂನ್ಯವಲ್ಲದ 3 × ಮೀ ಪದರಗಳ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಯಾವುದೇ n ಗೆ, ಗ್ರೇವರ್ ಆಧಾರದ ಯಾವುದೇ ಅಂಶದ ಪ್ರಕಾರವು ಗರಿಷ್ಠ g (m) ಆಗಿರುತ್ತದೆ ಎಂದು ಒಂದು ಸೀಮಿತ ಗ್ರೇವರ್ ಸಂಕೀರ್ಣತೆ ಕಾರ್ಯ g (m) ಇದೆ ಎಂದು ಅದು ತಿರುಗುತ್ತದೆ. ಗ್ರೇವರ್ ಆಧಾರವು ಗ್ರೇವರ್ ಆಧಾರದ ಸೂಕ್ತವಾದ ಹುದುಗಿರುವ ಪ್ರತಿಗಳ ಸಂಯೋಜನೆಯಾಗಿದೆ ಎಂದು ಅದು ಅನುಸರಿಸುತ್ತದೆ. ಪ್ರಾಯೋಗಿಕವಾಗಿ ಅನಿಯಂತ್ರಿತ ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯನ್ನು ಸರಿಸುಮಾರು ಪರಿಹರಿಸಲು, ಈ ಕೆಳಗಿನಂತೆ ಮುಂದುವರಿಯಿರಿ. ಮೇಲೆ ತಿಳಿಸಿದ ಸಾರ್ವತ್ರಿಕತೆಯಿಂದ ಸಕ್ರಿಯಗೊಳಿಸಲಾದ ಸೂಕ್ತವಾದ 3 × m × n ಟೇಬಲ್ ಸಮಸ್ಯೆಯಲ್ಲಿ ಮೊದಲು ಅದನ್ನು ಹುದುಗಿಸಿ. ಈಗ ಅಂದಾಜುಗಳ ಈ ಕೆಳಗಿನ ಶ್ರೇಣಿಯನ್ನು ಅನ್ವಯಿಸಿ. ಈ ಶ್ರೇಣಿಯ k ಮಟ್ಟದಲ್ಲಿ, ಗರಿಷ್ಠ k ನಲ್ಲಿ ಆ ರೀತಿಯ ಅಂಶಗಳನ್ನು ಮಾತ್ರ ಒಳಗೊಂಡಿರುವ ಉಪವಿಭಾಗವಾಗಿರಲಿ; 3 × m × n ಟೇಬಲ್ ಸಮಸ್ಯೆಯಲ್ಲಿ ಹುದುಗಿರುವ ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗೆ ಸಾಧ್ಯವಾದಷ್ಟು ಉತ್ತಮವಾದ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಬಿಂದುವನ್ನು ಪಡೆಯಲು ಸಾಧ್ಯವಾದಷ್ಟು ಕಾಲ ಪುನರಾವರ್ತಿತ ಅಲ್ಗಾರಿದಮ್ನಲ್ಲಿ ಈ ಅಂದಾಜನ್ನು ಬಳಸಿ; ಈ ಬಿಂದುವಿನ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯ ಮೌಲ್ಯವು ತೃಪ್ತಿಕರವಾಗಿದ್ದರೆ (ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ವಿಶ್ರಾಂತಿಯ ಮೌಲ್ಯಕ್ಕೆ ಹೋಲಿಸಿದರೆ), ನಂತರ ಈ ಬಿಂದುವನ್ನು ಬಳಸಿ; ಇಲ್ಲದಿದ್ದರೆ k ಅನ್ನು ಹೆಚ್ಚಿಸಿ ಮತ್ತು ಶ್ರೇಣಿಯ ಮುಂದಿನ ಹಂತಕ್ಕೆ ಮುಂದುವರಿಯಿರಿ. ಯಾವುದೇ ಸ್ಥಿರ ಮಟ್ಟದ k ಗೆ, ಗ್ರೇವರ್ ಆಧಾರದ ಅಂದಾಜು ಬಹುಪದ ಕಾರ್ಡಿನಲಿಟಿಯನ್ನು ಹೊಂದಿದೆ ಮತ್ತು ಅದನ್ನು ಅಷ್ಟು ಸಮಯದಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು ಎಂದು ತೋರಿಸಬಹುದು. ಸ್ಥಿರ ನಿಯತಾಂಕ ಟ್ರ್ಯಾಕ್ಟಬಿಲಿಟಿಃ ಬಹುಪದಿಯಿಂದ ಘನ ಸಮಯದ ಸಂಕೀರ್ಣತೆ ಮೇಲೆ ಚರ್ಚಿಸಲಾದ ಕೆಲವು ಅನ್ವಯಿಕೆಗಳನ್ನು ಪರಿಹರಿಸುವ ಸಮಯದ ಸಂಕೀರ್ಣತೆ, ಉದಾಹರಣೆಗೆ ಬಹು-ಆಯಾಮದ ಕೋಷ್ಟಕ ಸಮಸ್ಯೆಗಳು, ಬಹು-ಹೊಂದಾಣಿಕೆಯ ಹರಿವಿನ ಸಮಸ್ಯೆಗಳು ಮತ್ತು ಎನ್-ಪಟ್ಟು ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳು, ಸಂಬಂಧಿತ ಗ್ರೇವರ್ ಆಧಾರದ ಕಾರ್ಡಿನಾಲಿಟಿಯಿಂದ ಪ್ರಾಬಲ್ಯ ಹೊಂದಿದೆ, ಇದು ಸಾಮಾನ್ಯವಾಗಿ ದೊಡ್ಡ ಡಿಗ್ರಿ ಜಿ ಹೊಂದಿರುವ ಬಹುಪದವಾಗಿದೆ, ಇದು ವ್ಯವಸ್ಥೆಯ ಸೂಕ್ತವಾದ ಗ್ರೇವರ್ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ. ಹೆಚ್ಚು ವೇಗವಾಗಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಲಾಗುತ್ತದೆ, ಇದು ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ x + qg ಅನ್ನು q ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕದೊಂದಿಗೆ ಮತ್ತು g ಅಂಶದೊಂದಿಗೆ ಗ್ರೇವರ್ ಆಧಾರವನ್ನು ಸ್ಪಷ್ಟವಾಗಿ ನಿರ್ಮಿಸದೆ, ಕ್ಯೂಬಿಕ್ ಸಮಯದಲ್ಲಿ ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ನಿಯತಾಂಕ ಸಂಕೀರ್ಣತೆಯ ಪರಿಭಾಷೆಯಲ್ಲಿ, ಸೂಕ್ತವಾಗಿ ನಿಯತಾಂಕಗೊಳಿಸಲಾದ ಈ ಎಲ್ಲಾ ಸಮಸ್ಯೆಗಳು ಮತ್ತು ನಿರ್ದಿಷ್ಟವಾಗಿ l ಮತ್ತು m ನಿಂದ ನಿಯತಾಂಕಗೊಳಿಸಲಾದ l × m × n ಕೋಷ್ಟಕದ ಸಮಸ್ಯೆಗಳು ಸ್ಥಿರವಾದ ನಿಯತಾಂಕಗಳಾಗಿರುತ್ತವೆ ಎಂದು ಇದು ಸೂಚಿಸುತ್ತದೆ. ಪೂರ್ಣಾಂಕ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳ ಶೂನ್ಯ ಸೆಟ್ಗಳಿಗೆ ಸಂಬಂಧಿಸಿದ ಮತ್ತೊಂದು ಸಾಧನವಾದ ಗೋರ್ಡಾನ್ನ ಲೆಮ್ಮಾವನ್ನು ಸಹ ನೋಡಿ. ಉಲ್ಲೇಖಗಳು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್