Partition problem
ಸಂಖ್ಯೆ ಸಿದ್ಧಾಂತ ಮತ್ತು ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನದಲ್ಲಿ, ವಿಭಜನಾ ಸಮಸ್ಯೆ ಅಥವಾ ಸಂಖ್ಯೆ ವಿಭಜನೆಯು, ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ನಿರ್ದಿಷ್ಟ ಬಹು-ಸಮೂಹ S ಅನ್ನು S1 ಮತ್ತು S2 ಎಂಬ ಎರಡು ಉಪಗುಂಪುಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದೇ ಎಂದು ನಿರ್ಧರಿಸುವ ಕಾರ್ಯವಾಗಿದೆ, ಅಂದರೆ S1 ನಲ್ಲಿನ ಸಂಖ್ಯೆಗಳ ಮೊತ್ತವು S2 ನಲ್ಲಿನ ಸಂಖ್ಯೆಗಳ ಮೊತ್ತಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿದ್ದರೂ, ಹುಸಿ-ಬಹುಪದೀಯ ಸಮಯದ ಕ್ರಿಯಾತ್ಮಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಪರಿಹಾರವಿದೆ, ಮತ್ತು ಅನೇಕ ಸಂದರ್ಭಗಳಲ್ಲಿ ಸಮಸ್ಯೆಯನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿ ಅಥವಾ ಸರಿಸುಮಾರು ಪರಿಹರಿಸುವ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ಗಳಿವೆ. ಈ ಕಾರಣಕ್ಕಾಗಿ, ಇದನ್ನು "ಅತ್ಯಂತ ಸುಲಭವಾದ ಸಮಸ್ಯೆ" ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯ ಆಪ್ಟಿಮೈಸೇಶನ್ ಆವೃತ್ತಿಯಿದೆ, ಇದು ಮಲ್ಟಿಸೆಟ್ ಎಸ್ ಅನ್ನು ಎಸ್ 1, ಎಸ್ 2 ಎಂಬ ಎರಡು ಉಪಗುಂಪುಗಳಾಗಿ ವಿಭಜಿಸುವುದು, ಅಂದರೆ ಎಸ್ 1 ನಲ್ಲಿನ ಅಂಶಗಳ ಮೊತ್ತ ಮತ್ತು ಎಸ್ 2 ನಲ್ಲಿನ ಅಂಶಗಳ ಮೊತ್ತದ ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತದೆ. ಆಪ್ಟಿಮೈಸೇಶನ್ ಆವೃತ್ತಿಯು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿದೆ, ಆದರೆ ಆಚರಣೆಯಲ್ಲಿ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಪರಿಹರಿಸಬಹುದು. ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯು ಎರಡು ಸಂಬಂಧಿತ ಸಮಸ್ಯೆಗಳ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆಃ ಉಪಗುಂಪು ಮೊತ್ತದ ಸಮಸ್ಯೆಯಲ್ಲಿ, S ನ ಉಪಗುಂಪನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಗುರಿಯಾಗಿದೆ, ಅದರ ಮೊತ್ತವು ಇನ್ಪುಟ್ ಆಗಿ ನೀಡಲಾದ ನಿರ್ದಿಷ್ಟ ಗುರಿ ಸಂಖ್ಯೆ T ಆಗಿದೆ (ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯು ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದ್ದು ಇದರಲ್ಲಿ T ಎಂಬುದು S ನ ಅರ್ಧ ಮೊತ್ತವಾಗಿದೆ). ಬಹುಮಾರ್ಗ ಸಂಖ್ಯೆ ವಿಭಜನೆಯಲ್ಲಿ, ಒಂದು ಪೂರ್ಣಾಂಕ ನಿಯತಾಂಕ k ಇರುತ್ತದೆ, ಮತ್ತು S ಅನ್ನು ಸಮಾನ ಮೊತ್ತದ k ಉಪಗುಂಪುಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು ಗುರಿಯಾಗಿದೆ (ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯು k = 2 ರ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆ). ಆದಾಗ್ಯೂ, ಇದು 3-ವಿಭಜನೆಯ ಸಮಸ್ಯೆಗಿಂತ ಸಾಕಷ್ಟು ಭಿನ್ನವಾಗಿದೆಃ ಆ ಸಮಸ್ಯೆಯಲ್ಲಿ, ಉಪಗುಂಪುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಮುಂಚಿತವಾಗಿ ನಿಗದಿಪಡಿಸಲಾಗಿಲ್ಲ-ಇದು |S |/3 ಆಗಿರಬೇಕು, ಅಲ್ಲಿ ಪ್ರತಿ ಉಪಗುಂಪು ನಿಖರವಾಗಿ 3 ಅಂಶಗಳನ್ನು ಹೊಂದಿರಬೇಕು. 3-ವಿಭಜನೆಯು ವಿಭಜನೆಗಿಂತ ತುಂಬಾ ಕಠಿಣವಾಗಿದೆ-ಇದು P = NP ಹೊರತು ಯಾವುದೇ ಹುಸಿ-ಬಹುಪದೀಯ ಸಮಯದ ಕ್ರಮಾವಳಿಗಳನ್ನು ಹೊಂದಿಲ್ಲ. S = {3,1,1,2,2,1} ನೀಡಿದ ಉದಾಹರಣೆಗಳಲ್ಲಿ, ವಿಭಜನೆಯ ಸಮಸ್ಯೆಗೆ ಮಾನ್ಯವಾದ ಪರಿಹಾರವೆಂದರೆ S1 = {1,1,1,2} ಮತ್ತು S2 = {{2,3} ಎಂಬ ಎರಡು ಸೆಟ್ಗಳು. ಎರಡೂ ಸೆಟ್ಗಳ ಮೊತ್ತವು 5 ಆಗಿರುತ್ತದೆ, ಮತ್ತು ಅವು ಎಸ್ ಅನ್ನು ವಿಭಜಿಸುತ್ತವೆ. ಈ ಪರಿಹಾರವು ಅನನ್ಯವಾಗಿಲ್ಲ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. S1 = {3,1,1} ಮತ್ತು S2 = {2,2,1} ಮತ್ತೊಂದು ಪರಿಹಾರವಾಗಿದೆ. ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕಗಳ ಪ್ರತಿಯೊಂದು ಬಹುವಿಭಾಗವು ಸಮಾನ ಮೊತ್ತದೊಂದಿಗೆ ಎರಡು ಉಪಗುಂಪುಗಳಾಗಿ ವಿಭಜನೆಯನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. ಅಂತಹ ಗುಂಪಿಗೆ ಒಂದು ಉದಾಹರಣೆಯೆಂದರೆ S = {2,5}. ಕಂಪ್ಯೂಟೇಶನಲ್ ಗಡಸುತನ ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ. ಗಟ್ಟಿಯಾಗಿರುತ್ತದೆ. ಉಪಗುಂಪು ಮೊತ್ತದ ಸಮಸ್ಯೆಯಿಂದ ಕಡಿತಗೊಳಿಸುವ ಮೂಲಕ ಇದನ್ನು ಸಾಬೀತುಪಡಿಸಬಹುದು. ಉಪವಿಭಾಗದ ಮೊತ್ತದ ಒಂದು ಉದಾಹರಣೆಯು ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಸೆಟ್ S ಮತ್ತು ಗುರಿ ಮೊತ್ತ T ಅನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ; ನಿಖರವಾಗಿ T ಮೊತ್ತದೊಂದಿಗೆ S ನ ಉಪವಿಭಾಗವಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು ಗುರಿಯಾಗಿದೆ. ಅಂತಹ ಒಂದು ಉದಾಹರಣೆಯನ್ನು ನೀಡಿದರೆ, ವಿಭಜನೆಯ ಒಂದು ಉದಾಹರಣೆಯನ್ನು ನಿರ್ಮಿಸಿ, ಇದರಲ್ಲಿ ಇನ್ಪುಟ್ ಸೆಟ್ ಮೂಲ ಸೆಟ್ ಜೊತೆಗೆ ಎರಡು ಅಂಶಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆಃ z1 ಮತ್ತು z2, z1 = ಮೊತ್ತ (S) ಮತ್ತು z2 = 2T. ಈ ಇನ್ಪುಟ್ ಗುಂಪಿನ ಮೊತ್ತವು ಮೊತ್ತ (S) + z1 + z2 = 2 ಮೊತ್ತ (S) + 2T ಆಗಿದೆ, ಆದ್ದರಿಂದ ವಿಭಜನೆಯ ಗುರಿ ಮೊತ್ತವು ಮೊತ್ತ (S) + T ಆಗಿದೆ. ನಂತರ ಮೊತ್ತ (S′) = T, ಆದ್ದರಿಂದ ಮೊತ್ತ (S′z _ 1) = ಮೊತ್ತ (S) + T, ಆದ್ದರಿಂದ S′z _ 1 ವಿಭಜನೆಯ ನಿದರ್ಶನಕ್ಕೆ ಪರಿಹಾರವಾಗಿದೆ. ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ವಿಭಜನೆಯ ನಿದರ್ಶನಕ್ಕೆ ಎಸ್ "ಪರಿಹಾರವಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ನಂತರ, S′ಯು z1 ಅಥವಾ z2ಅನ್ನು ಹೊಂದಿರಬೇಕು, ಆದರೆ ಎರಡನ್ನೂ ಹೊಂದಿರಬಾರದು, ಏಕೆಂದರೆ ಅವುಗಳ ಮೊತ್ತವು ಮೊತ್ತ (S) + T ಗಿಂತ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. S "ಯು z2 ಅನ್ನು ಹೊಂದಿದ್ದರೆ, ಅದು ನಿಖರವಾದ ಮೊತ್ತ (S) − T ಯ ಮೊತ್ತದೊಂದಿಗೆ S ನಿಂದ ಅಂಶಗಳನ್ನು ಹೊಂದಿರಬೇಕು, ಆದ್ದರಿಂದ S ನಲ್ಲಿರುವ ಇತರ ವಸ್ತುಗಳು ಉಪಗುಂಪು ನಿದರ್ಶನಕ್ಕೆ ಪರಿಹಾರವಾಗಿರುತ್ತವೆ. ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳು ಮೇಲೆ ತಿಳಿಸಿದಂತೆ, ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯು ಬಹುಪಥ ವಿಭಜನೆ ಮತ್ತು ಉಪಗುಂಪು-ಮೊತ್ತದ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆ. ಆದ್ದರಿಂದ, ಈ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆಗಳಿಗೆ ಅಭಿವೃದ್ಧಿಪಡಿಸಿದ ಕ್ರಮಾವಳಿಗಳಿಂದ ಇದನ್ನು ಪರಿಹರಿಸಬಹುದು. ಬಹುಮಾರ್ಗ ಸಂಖ್ಯೆ ವಿಭಜನೆಗಾಗಿ ಅಭಿವೃದ್ಧಿಪಡಿಸಲಾದ ಕ್ರಮಾವಳಿಗಳು ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಒಳಗೊಂಡಿವೆಃ ದುರಾಸೆಯ ಸಂಖ್ಯೆ ವಿಭಜನೆ-ಸಂಖ್ಯೆಗಳ ಮೇಲೆ ಲೂಪ್ಗಳು, ಮತ್ತು ಪ್ರಸ್ತುತ ಮೊತ್ತವು ಚಿಕ್ಕದಾದ ಸೆಟ್ನಲ್ಲಿ ಪ್ರತಿ ಸಂಖ್ಯೆಯನ್ನು ಇರಿಸುತ್ತದೆ. ಸಂಖ್ಯೆಗಳನ್ನು ವಿಂಗಡಿಸದಿದ್ದರೆ, ರನ್ಟೈಮ್ ಒ (ಎನ್) ಆಗಿರುತ್ತದೆ ಮತ್ತು ಅಂದಾಜು ಅನುಪಾತವು ಗರಿಷ್ಠ 3/2 ಆಗಿರುತ್ತದೆ ("ಅಂದಾಜು ಅನುಪಾತ" ಎಂದರೆ ಅಲ್ಗಾರಿದಮ್ ಔಟ್ಪುಟ್ನಲ್ಲಿ ದೊಡ್ಡ ಮೊತ್ತ, ಸೂಕ್ತವಾದ ವಿಭಜನೆಯಲ್ಲಿ ದೊಡ್ಡ ಮೊತ್ತದಿಂದ ಭಾಗಿಸಲಾಗಿದೆ). ಸಂಖ್ಯೆಗಳನ್ನು ವಿಂಗಡಿಸುವುದರಿಂದ ರನ್ ಟೈಮ್ ಅನ್ನು ಒ (ಎನ್ ಲಾಗ್ ಎನ್) ಗೆ ಹೆಚ್ಚಿಸುತ್ತದೆ ಮತ್ತು ಅಂದಾಜು ಅನುಪಾತವನ್ನು 7/6 ಗೆ ಸುಧಾರಿಸುತ್ತದೆ. ಸಂಖ್ಯೆಗಳನ್ನು [0,1] ರಲ್ಲಿ ಏಕರೂಪವಾಗಿ ವಿತರಿಸಿದರೆ, ಅಂದಾಜು ಅನುಪಾತವು ಬಹುತೇಕ ಖಚಿತವಾಗಿ ಮತ್ತು ನಿರೀಕ್ಷೆಯಲ್ಲಿರುತ್ತದೆ. ಅತಿದೊಡ್ಡ ಡಿಫರೆನ್ಸಿಂಗ್ ವಿಧಾನವು (ಕರ್ಮಾರ್ಕರ್-ಕಾರ್ಪ್ ಅಲ್ಗಾರಿದಮ್ ಎಂದೂ ಕರೆಯಲ್ಪಡುತ್ತದೆ) ಸಂಖ್ಯೆಗಳನ್ನು ಅವರೋಹಣ ಕ್ರಮದಲ್ಲಿ ವಿಂಗಡಿಸುತ್ತದೆ ಮತ್ತು ಅವುಗಳ ವ್ಯತ್ಯಾಸಗಳಿಂದ ಸಂಖ್ಯೆಗಳನ್ನು ಪದೇ ಪದೇ ಬದಲಾಯಿಸುತ್ತದೆ. ರನ್ಟೈಮ್ ಸಂಕೀರ್ಣತೆಯು ಒ (ಎನ್ ಲಾಗ್ ಎನ್) ಆಗಿದೆ. ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, ಅದರ ಅಂದಾಜು ಅನುಪಾತವು ಒಂದೇ ಆಗಿರುತ್ತದೆ-ಗರಿಷ್ಠ 7/6. ಆದಾಗ್ಯೂ, ಸರಾಸರಿ ಸಂದರ್ಭದಲ್ಲಿ ಇದು ದುರಾಸೆಯ ಕ್ರಮಾವಳಿಗಿಂತ ಉತ್ತಮವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆಃ ಸಂಖ್ಯೆಗಳನ್ನು [0,1] ನಲ್ಲಿ ಏಕರೂಪವಾಗಿ ವಿತರಿಸಿದಾಗ, ಅದರ ಅಂದಾಜು ಅನುಪಾತವು ನಿರೀಕ್ಷೆಯಲ್ಲಿರುತ್ತದೆ. ಇದು ಸಿಮ್ಯುಲೇಶನ್ ಪ್ರಯೋಗಗಳಲ್ಲಿಯೂ ಉತ್ತಮವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಮಲ್ಟಿಫಿಟ್ ಅಲ್ಗಾರಿದಮ್ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ಗಾಗಿ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಬಳಸುತ್ತದೆ. ಅತ್ಯಂತ ಕೆಟ್ಟ ಪರಿಸ್ಥಿತಿಯಲ್ಲಿ, ಅದರ ಅಂದಾಜು ಅನುಪಾತವು 8/7 ಆಗಿದೆ. ಉಪಗುಂಪು ಮೊತ್ತದ ಸಮಸ್ಯೆಯು ಎಫ್. ಪಿ. ಟಿ. ಎ. ಎಸ್ ಅನ್ನು ಹೊಂದಿದ್ದು, ಇದನ್ನು ಗುರಿ ಮೊತ್ತವನ್ನು ಮೊತ್ತ (ಎಸ್)/2 ಎಂದು ನಿಗದಿಪಡಿಸುವ ಮೂಲಕ ವಿಭಜನೆಯ ಸಮಸ್ಯೆಗೂ ಬಳಸಬಹುದು. ನಿಖರವಾದ ಕ್ರಮಾವಳಿಗಳು ಯಾವಾಗಲೂ ಸೂಕ್ತವಾದ ವಿಭಾಗವನ್ನು ಕಂಡುಕೊಳ್ಳುವ ನಿಖರವಾದ ಕ್ರಮಾವಳಿಗಳಿವೆ. ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿರುವುದರಿಂದ, ಅಂತಹ ಕ್ರಮಾವಳಿಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಘಾತೀಯ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು, ಆದರೆ ಕೆಲವು ಸಂದರ್ಭಗಳಲ್ಲಿ ಪ್ರಾಯೋಗಿಕವಾಗಿ ಬಳಸಬಹುದಾಗಿದೆ. ಬಹುಮಾರ್ಗ ಸಂಖ್ಯೆ ವಿಭಜನೆಗಾಗಿ ಅಭಿವೃದ್ಧಿಪಡಿಸಲಾದ ಕ್ರಮಾವಳಿಗಳು ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಒಳಗೊಂಡಿವೆಃ ಸೂಡೊಪಾಲಿನೋಮಿಯಲ್ ಸಮಯ ಸಂಖ್ಯೆ ವಿಭಜನೆಯು ಮೆಮೊರಿಯನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಇದು ಇನ್ಪುಟ್ನಲ್ಲಿನ ಅತಿದೊಡ್ಡ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಕಂಪ್ಲೀಟ್ ಗ್ರೀಡಿ ಅಲ್ಗಾರಿದಮ್ (ಸಿಜಿಎ) ಬೈನರಿ ಮರವನ್ನು ನಿರ್ಮಿಸುವ ಮೂಲಕ ಎಲ್ಲಾ ವಿಭಾಗಗಳನ್ನು ಪರಿಗಣಿಸುತ್ತದೆ. ಮರದ ಪ್ರತಿಯೊಂದು ಹಂತವು ಇನ್ಪುಟ್ ಸಂಖ್ಯೆಗೆ ಅನುರೂಪವಾಗಿದೆ, ಅಲ್ಲಿ ಮೂಲವು ಅತಿದೊಡ್ಡ ಸಂಖ್ಯೆಗೆ, ಕೆಳಗಿನ ಮಟ್ಟವು ಮುಂದಿನ ಅತಿದೊಡ್ಡ ಸಂಖ್ಯೆಗೆ ಅನುರೂಪವಾಗಿದೆ. ಪ್ರತಿ ಶಾಖೆಯು ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಯನ್ನು ಹಾಕಬಹುದಾದ ವಿಭಿನ್ನ ಗುಂಪಿಗೆ ಅನುರೂಪವಾಗಿದೆ. ಮರವನ್ನು ಆಳವಾದ-ಮೊದಲ ಕ್ರಮದಲ್ಲಿ ಹಾದುಹೋಗಲು ಕೇವಲ ಸ್ಥಳಾವಕಾಶ ಬೇಕಾಗುತ್ತದೆ, ಆದರೆ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ದುರಾಸೆಯ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅನ್ನು ಬಳಸುವ ಮೂಲಕ ರನ್ಟೈಮ್ ಅನ್ನು ಸುಧಾರಿಸಬಹುದುಃ ಪ್ರತಿ ಹಂತದಲ್ಲೂ, ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಯನ್ನು ಸಣ್ಣ ಮೊತ್ತದೊಂದಿಗೆ ಸೆಟ್ನಲ್ಲಿ ಇರಿಸಲಾಗಿರುವ ಶಾಖೆಯನ್ನು ಮೊದಲು ಅಭಿವೃದ್ಧಿಪಡಿಸಿ. ಈ ಅಲ್ಗಾರಿದಮ್ ಮೊದಲು ದುರಾಸೆಯ ಸಂಖ್ಯೆ ವಿಭಜನೆಯಿಂದ ಕಂಡುಬರುವ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ, ಆದರೆ ನಂತರ ಉತ್ತಮ ಪರಿಹಾರಗಳನ್ನು ಹುಡುಕಲು ಮುಂದುವರಿಯುತ್ತದೆ. ಈ ಕಲ್ಪನೆಯ ಕೆಲವು ವ್ಯತ್ಯಾಸಗಳು ಉಪಗುಂಪು-ಮೊತ್ತದ ಸಮಸ್ಯೆಗೆ ಸಂಪೂರ್ಣ ಬಹುಪದ-ಸಮಯದ ಅಂದಾಜು ಯೋಜನೆಗಳಾಗಿವೆ, ಮತ್ತು ಆದ್ದರಿಂದ ವಿಭಜನೆಯ ಸಮಸ್ಯೆಗೂ ಸಹ. ಕಂಪ್ಲೀಟ್ ಕರ್ಮಾರ್ಕರ್-ಕಾರ್ಪ್ ಅಲ್ಗಾರಿದಮ್ (ಸಿಕೆಕೆ) ಬೈನರಿ ಮರವನ್ನು ನಿರ್ಮಿಸುವ ಮೂಲಕ ಎಲ್ಲಾ ವಿಭಾಗಗಳನ್ನು ಪರಿಗಣಿಸುತ್ತದೆ. ಪ್ರತಿ ಹಂತವು ಒಂದು ಜೋಡಿ ಸಂಖ್ಯೆಗಳಿಗೆ ಅನುರೂಪವಾಗಿದೆ. ಎಡ ಶಾಖೆಯು ಅವುಗಳನ್ನು ವಿವಿಧ ಉಪಗುಂಪುಗಳಲ್ಲಿ ಇರಿಸುವುದಕ್ಕೆ ಅನುರೂಪವಾಗಿದೆ (ಅಂದರೆ, ಅವುಗಳ ವ್ಯತ್ಯಾಸದಿಂದ ಅವುಗಳನ್ನು ಬದಲಾಯಿಸುವುದು), ಮತ್ತು ಬಲ ಶಾಖೆಯು ಅವುಗಳನ್ನು ಒಂದೇ ಉಪಗುಂಪಿನಲ್ಲಿ ಇರಿಸುವುದಕ್ಕೆ ಅನುರೂಪವಾಗಿದೆ (ಅಂದರೆ, ಅವುಗಳನ್ನು ಅವುಗಳ ಮೊತ್ತದಿಂದ ಬದಲಾಯಿಸುವುದು). ಈ ಅಲ್ಗಾರಿದಮ್ ಮೊದಲು ಅತಿದೊಡ್ಡ ಡಿಫರೆನ್ಸಿಂಗ್ ವಿಧಾನದಿಂದ ಕಂಡುಬರುವ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ, ಆದರೆ ನಂತರ ಉತ್ತಮ ಪರಿಹಾರಗಳನ್ನು ಕಂಡುಕೊಳ್ಳಲು ಮುಂದುವರಿಯುತ್ತದೆ. ಇದು ಯಾದೃಚ್ಛಿಕ ಸಂದರ್ಭಗಳಲ್ಲಿ ಸಿಜಿಎಗಿಂತ ಗಣನೀಯವಾಗಿ ವೇಗವಾಗಿ ಚಲಿಸುತ್ತದೆ. ಸಮಾನ ವಿಭಾಗವು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದಾಗ ಅದರ ಪ್ರಯೋಜನವು ತುಂಬಾ ದೊಡ್ಡದಾಗಿದೆ, ಮತ್ತು ಇದು ಹಲವಾರು ಪ್ರಮಾಣದ ಕ್ರಮಗಳಾಗಿರಬಹುದು. ಆಚರಣೆಯಲ್ಲಿ, ಸಂಖ್ಯೆಗಳು ಗರಿಷ್ಠ 12 ಗಮನಾರ್ಹ ಅಂಕೆಗಳನ್ನು ಹೊಂದಿದ್ದರೆ ಅನಿಯಂತ್ರಿತ ಗಾತ್ರದ ಸಮಸ್ಯೆಗಳನ್ನು ಸಿಕೆಕೆ ಮೂಲಕ ಪರಿಹರಿಸಬಹುದು. ಸಿಕೆಕೆ ಯಾವುದೇ ಸಮಯದಲ್ಲಿ ಅಲ್ಗಾರಿದಮ್ ಆಗಿಯೂ ಕಾರ್ಯನಿರ್ವಹಿಸಬಹುದುಃ ಇದು ಮೊದಲು ಕೆಕೆ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ, ಮತ್ತು ನಂತರ ಸಮಯ ಅನುಮತಿಸಿದಂತೆ ಕ್ರಮೇಣ ಉತ್ತಮ ಪರಿಹಾರಗಳನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ (ಬಹುಶಃ ಅತ್ಯುತ್ತಮತೆಯನ್ನು ತಲುಪಲು ಘಾತೀಯ ಸಮಯ ಬೇಕಾಗುತ್ತದೆ, ಕೆಟ್ಟ ಸಂದರ್ಭಗಳಲ್ಲಿ). ಇದಕ್ಕೆ ಸ್ಥಳಾವಕಾಶ ಬೇಕಾಗುತ್ತದೆ, ಆದರೆ ಕೆಟ್ಟ ಪರಿಸ್ಥಿತಿಯಲ್ಲಿ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ಉಪಗುಂಪು ಮೊತ್ತಕ್ಕಾಗಿ ಅಭಿವೃದ್ಧಿಪಡಿಸಲಾದ ಕ್ರಮಾವಳಿಗಳು ಹೀಗಿವೆಃ ಹೊರೋವಿಟ್ಜ್ ಮತ್ತು ಸನಹಿ-ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಚಲಿಸುತ್ತವೆ, ಆದರೆ ಸ್ಥಳಾವಕಾಶದ ಅಗತ್ಯವಿರುತ್ತದೆ. ಶ್ರೋಪೆಲ್ ಮತ್ತು ಶಮೀರ್-ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಓಡುತ್ತಾರೆ ಮತ್ತು ಅವರಿಗೆ ಕಡಿಮೆ ಸ್ಥಳಾವಕಾಶ ಬೇಕಾಗುತ್ತದೆ. ಹೌಗ್ರೇವ್-ಗ್ರಹಾಂ ಮತ್ತು ಜೌಕ್ಸ್-ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತವೆ, ಆದರೆ ಇದು ಯಾದೃಚ್ಛಿಕ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದ್ದು ಅದು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯನ್ನು ಮಾತ್ರ ಪರಿಹರಿಸುತ್ತದೆ (ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯಲ್ಲ). ಹಾರ್ಡ್ ನಿದರ್ಶನಗಳು ಮತ್ತು ಹಂತ-ಪರಿವರ್ತನೆಯ ಸೆಟ್ಗಳು ಅವುಗಳ ಇನ್ಪುಟ್ ಗಾತ್ರಗಳಿಗೆ ಹೋಲಿಸಿದರೆ ಕೇವಲ ಒಂದು, ಅಥವಾ ಯಾವುದೇ ವಿಭಾಗಗಳಿಲ್ಲದೆ ಪರಿಹರಿಸಲು ಕಷ್ಟವಾಗುತ್ತದೆ (ಅಥವಾ ಅತ್ಯಂತ ದುಬಾರಿಯಾಗಿದೆ). ಗುಂಪಿನ ಗಾತ್ರಕ್ಕೆ ಹೋಲಿಸಿದರೆ ಮೌಲ್ಯಗಳು ಚಿಕ್ಕದಾಗಿದ್ದರೆ, ಪರಿಪೂರ್ಣ ವಿಭಾಗಗಳ ಸಾಧ್ಯತೆ ಹೆಚ್ಚು. ಈ ಸಮಸ್ಯೆಯು "ಹಂತದ ಪರಿವರ್ತನೆಗೆ" ಒಳಗಾಗುತ್ತದೆ ಎಂದು ತಿಳಿದುಬಂದಿದೆ; ಕೆಲವು ಸೆಟ್ಗಳಿಗೆ ಸಾಧ್ಯತೆ ಮತ್ತು ಇತರರಿಗೆ ಅಸಂಭವವಾಗಿದೆ. m ಎಂಬುದು ಗುಂಪಿನಲ್ಲಿನ ಯಾವುದೇ ಸಂಖ್ಯೆಯನ್ನು ವ್ಯಕ್ತಪಡಿಸಲು ಅಗತ್ಯವಿರುವ ಬಿಟ್ಗಳ ಸಂಖ್ಯೆಯಾಗಿದ್ದರೆ ಮತ್ತು n ಎಂಬುದು ಗುಂಪಿನ ಗಾತ್ರವಾಗಿದ್ದರೆ, ಅದು ಅನೇಕ ಪರಿಹಾರಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಕಡಿಮೆ ಅಥವಾ ಯಾವುದೇ ಪರಿಹಾರಗಳನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. n ಮತ್ತು m ದೊಡ್ಡದಾಗುತ್ತಿದ್ದಂತೆ, ಪರಿಪೂರ್ಣ ವಿಭಾಗದ ಸಂಭವನೀಯತೆಯು ಅನುಕ್ರಮವಾಗಿ 1 ಅಥವಾ 0 ಕ್ಕೆ ಹೋಗುತ್ತದೆ. ಇದನ್ನು ಮೂಲತಃ ಜೆಂಟ್ ಮತ್ತು ವಾಲ್ಷ್ ಅವರ ಪ್ರಾಯೋಗಿಕ ಪುರಾವೆಗಳ ಆಧಾರದ ಮೇಲೆ ವಾದಿಸಲಾಯಿತು, ನಂತರ ಮೆರ್ಟೆನ್ಸ್ ಅವರು ಸಂಖ್ಯಾಶಾಸ್ತ್ರೀಯ ಭೌತಶಾಸ್ತ್ರದ ವಿಧಾನಗಳನ್ನು ಬಳಸಿದರು ಮತ್ತು ನಂತರ ಬೋರ್ಗ್ಸ್, ಚಾಯೆಸ್ ಮತ್ತು ಪಿಟೆಲ್ ಅವರು ಇದನ್ನು ಸಾಬೀತುಪಡಿಸಿದರು. ಸಂಭಾವ್ಯ ಆವೃತ್ತಿಯು ಜನ್ಮದಿನದ ವಿರೋಧಾಭಾಸಕ್ಕೆ ಸ್ವಲ್ಪಮಟ್ಟಿಗೆ ಹೋಲುವ ಒಂದು ಸಂಬಂಧಿತ ಸಮಸ್ಯೆಯೆಂದರೆ, ಇನ್ಪುಟ್ ಸೆಟ್ನ ಗಾತ್ರವನ್ನು ನಿರ್ಧರಿಸುವುದು, ಇದರಿಂದಾಗಿ ಸೆಟ್ನಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಯಾದೃಚ್ಛಿಕವಾಗಿ 1 ಮತ್ತು ಕೆಲವು ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯದ ನಡುವೆ ಏಕರೂಪದ ವಿತರಣೆಯೊಂದಿಗೆ ಆಯ್ಕೆ ಮಾಡಲಾಗಿದೆ ಎಂಬ ಊಹೆಯ ಅಡಿಯಲ್ಲಿ ಪರಿಹಾರವಿದೆ ಎಂದು ನಾವು ಅರ್ಧದಷ್ಟು ಸಂಭವನೀಯತೆಯನ್ನು ಹೊಂದಿದ್ದೇವೆ. ಈ ಸಮಸ್ಯೆಯ ಪರಿಹಾರವು ಹುಟ್ಟುಹಬ್ಬದ ವಿರೋಧಾಭಾಸದಂತೆ ವ್ಯತಿರಿಕ್ತವಾಗಿರಬಹುದು. ರೂಪಾಂತರಗಳು ಮತ್ತು ಸಾಮಾನ್ಯೀಕರಣಗಳು ಸಮಾನ-ಕಾರ್ಡಿನಲಿಟಿ ವಿಭಾಗವು ಒಂದು ರೂಪಾಂತರವಾಗಿದ್ದು, ಇದರಲ್ಲಿ ಎರಡೂ ಭಾಗಗಳು ಸಮಾನ ಮೊತ್ತವನ್ನು ಹೊಂದುವುದರ ಜೊತೆಗೆ ಸಮಾನ ಸಂಖ್ಯೆಯ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರಬೇಕು. ಈ ರೂಪಾಂತರವು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಆಗಿದೆ. ಪುರಾವೆ. ಕೆಲವು n ಸಂಖ್ಯೆಗಳೊಂದಿಗೆ ಪ್ರಮಾಣಿತ ವಿಭಜನೆಯ ನಿದರ್ಶನವನ್ನು ನೀಡಿದರೆ, n ಸೊನ್ನೆಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಸಮಾನ-ಕಾರ್ಡಿನಾಲಿಟಿ-ವಿಭಜನೆಯ ನಿದರ್ಶನವನ್ನು ನಿರ್ಮಿಸಿ. ಸ್ಪಷ್ಟವಾಗಿ, ಹೊಸ ನಿದರ್ಶನವು ಮೂಲ ನಿದರ್ಶನವು ಸಮಾನ-ಮೊತ್ತದ ವಿಭಾಗವನ್ನು ಹೊಂದಿದ್ದರೆ ಸಮಾನ-ಕಾರ್ಡಿನಲಿಟಿ ಸಮಾನ-ಮೊತ್ತದ ವಿಭಾಗವನ್ನು ಹೊಂದಿದೆ. ಸಮತೋಲಿತ ಸಂಖ್ಯೆಯ ವಿಭಜನೆಯನ್ನು ಸಹ ನೋಡಿ. ವಿಭಿನ್ನ ವಿಭಾಗವು ಎಲ್ಲಾ ಇನ್ಪುಟ್ ಪೂರ್ಣಾಂಕಗಳು ವಿಭಿನ್ನವಾಗಿರುವ ಒಂದು ರೂಪಾಂತರವಾಗಿದೆ. ಈ ರೂಪಾಂತರವು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಆಗಿದೆ. ಉತ್ಪನ್ನ ವಿಭಜನೆಯು ಪೂರ್ಣಾಂಕಗಳ ಗುಂಪನ್ನು ಒಂದೇ ಉತ್ಪನ್ನದೊಂದಿಗೆ (ಒಂದೇ ಮೊತ್ತಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿ) ಎರಡು ಸೆಟ್ಗಳಾಗಿ ವಿಭಜಿಸುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಈ ಸಮಸ್ಯೆಯು ಬಲವಾಗಿ ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ. ಕೊವಲ್ಯೋವ್ ಮತ್ತು ಪೆಷ್ ಅವರು ವಿಭಜನೆ-ರೀತಿಯ ಸಮಸ್ಯೆಗಳ ಎನ್. ಪಿ.-ಗಡಸುತನವನ್ನು ಸಾಬೀತುಪಡಿಸುವ ಸಾಮಾನ್ಯ ವಿಧಾನವನ್ನು ಚರ್ಚಿಸುತ್ತಾರೆ. ಅಪ್ಲಿಕೇಶನ್ಗಳು ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯ ಒಂದು ಅನ್ವಯವೆಂದರೆ ಚುನಾವಣೆಗಳ ಕುಶಲತೆ. ಮೂರು ಅಭ್ಯರ್ಥಿಗಳಿದ್ದಾರೆ ಎಂದು ಭಾವಿಸೋಣ (ಎ, ಬಿ ಮತ್ತು ಸಿ). ಅಂಕಗಳ ಆಧಾರದ ಮೇಲೆ ಮತದಾನದ ನಿಯಮವನ್ನು ಬಳಸಿಕೊಂಡು ಒಬ್ಬ ಅಭ್ಯರ್ಥಿಯನ್ನು ಆಯ್ಕೆ ಮಾಡಬೇಕು, ಉದಾಹರಣೆಗೆ. ವೀಟೋ ನಿಯಮ (ಪ್ರತಿ ಮತದಾರನು ಒಬ್ಬ ಅಭ್ಯರ್ಥಿಯನ್ನು ವೀಟೋ ಮಾಡುತ್ತಾನೆ ಮತ್ತು ಕಡಿಮೆ ವೀಟೋ ಹೊಂದಿರುವ ಅಭ್ಯರ್ಥಿಯು ಗೆಲ್ಲುತ್ತಾನೆ). ಒಂದು ಒಕ್ಕೂಟವು ಸಿ ಚುನಾಯಿತರಾಗುವುದನ್ನು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ಬಯಸಿದರೆ, ಅವರು ತಮ್ಮ ಮತಗಳನ್ನು ಎ ಮತ್ತು ಬಿ ನಡುವೆ ವಿಭಜಿಸಬೇಕು, ಇದರಿಂದಾಗಿ ಪ್ರತಿಯೊಬ್ಬರೂ ಪಡೆಯುವ ಅತಿ ಕಡಿಮೆ ಸಂಖ್ಯೆಯ ವೀಟೋಗಳನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಬಹುದು. ಮತಗಳನ್ನು ತೂಗಿಸಿದರೆ, ಸಮಸ್ಯೆಯನ್ನು ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯಾಗಿ ಕಡಿಮೆ ಮಾಡಬಹುದು, ಹೀಗಾಗಿ ಅದನ್ನು ಸಿಕೆಕೆ ಬಳಸಿ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಪರಿಹರಿಸಬಹುದು. ಅಂಕಗಳನ್ನು ಆಧರಿಸಿದ ಯಾವುದೇ ಮತದಾನದ ನಿಯಮಕ್ಕೂ ಇದು ಅನ್ವಯಿಸುತ್ತದೆ. ಟಿಪ್ಪಣಿಗಳು ಉಲ್ಲೇಖಗಳ ಸಂಖ್ಯೆ ವಿಭಜನೆ ದುರ್ಬಲವಾದ ಎನ್. ಪಿ.-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳು