Pseudo-polynomial time
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಸಂಖ್ಯಾತ್ಮಕ ಅಲ್ಗಾರಿದಮ್ ಸೂಡೋ-ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ, ಅದರ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವು ಇನ್ಪುಟ್ನ ಸಂಖ್ಯಾತ್ಮಕ ಮೌಲ್ಯದಲ್ಲಿ ಬಹುಪದಿಯಾಗಿದ್ದರೆ (ಇನ್ಪುಟ್ನಲ್ಲಿ ಇರುವ ಅತಿದೊಡ್ಡ ಪೂರ್ಣಾಂಕ)-ಆದರೆ ಇನ್ಪುಟ್ನ ಉದ್ದದಲ್ಲಿ ಅಗತ್ಯವಿಲ್ಲ (ಅದನ್ನು ಪ್ರತಿನಿಧಿಸಲು ಅಗತ್ಯವಿರುವ ಬಿಟ್ಗಳ ಸಂಖ್ಯೆ), ಇದು ಬಹುಪದೀಯ ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ಗಳಿಗೆ ಅನ್ವಯಿಸುತ್ತದೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಇನ್ಪುಟ್ನ ಸಂಖ್ಯಾತ್ಮಕ ಮೌಲ್ಯವು ಇನ್ಪುಟ್ ಉದ್ದದಲ್ಲಿ ಘಾತೀಯವಾಗಿರುತ್ತದೆ, ಅದಕ್ಕಾಗಿಯೇ ಸೂಡೋ-ಪಾಲಿನೋಮಿಯಲ್ ಟೈಮ್ ಅಲ್ಗಾರಿದಮ್ ಇನ್ಪುಟ್ ಉದ್ದಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುವುದಿಲ್ಲ. ತಿಳಿದಿರುವ ಸೂಡೋ-ಪಾಲಿನೋಮಿಯಲ್ ಟೈಮ್ ಅಲ್ಗಾರಿದಮ್ಗಳೊಂದಿಗಿನ ಎನ್ಪಿ-ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆಯನ್ನು ದುರ್ಬಲವಾಗಿ ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಒಂದು ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಯನ್ನು ಸೂಡೋ-ಪಾಲಿನೋಮಿಯಲ್ ಟೈಮ್ ಅಲ್ಗಾರಿದಮ್ನಿಂದ ಪರಿಹರಿಸಲಾಗುವುದಿಲ್ಲ ಎಂದು ಸಾಬೀತಾದರೆ ಅದನ್ನು ಬಲವಾಗಿ ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಬಲವಾದ/ದುರ್ಬಲ ರೀತಿಯ ಎನ್. ಪಿ.-ಗಡಸುತನವನ್ನು ಇದೇ ರೀತಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಪ್ರಾಥಮಿಕತೆಯ ಪರೀಕ್ಷೆಯ ಉದಾಹರಣೆಗಳು n ಸಂಖ್ಯೆಯು ಅವಿಭಾಜ್ಯವಾಗಿದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸುವ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಗಣಿಸಿ, ಯಾವುದೇ ಸಂಖ್ಯೆಯು ಸಮವಾಗಿ ಭಾಗಿಸುವುದಿಲ್ಲವೇ ಎಂದು ನಿಷ್ಕಪಟವಾಗಿ ಪರಿಶೀಲಿಸುವ ಮೂಲಕ. ಈ ವಿಧಾನವು ವಿಭಾಗಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು, ಇದು n ನ ಮೌಲ್ಯದಲ್ಲಿ ಉಪ-ರೇಖೀಯವಾಗಿರುತ್ತದೆ ಆದರೆ n ನ ಉದ್ದದಲ್ಲಿ ಘಾತೀಯವಾಗಿರುತ್ತದೆ (ಇದು ಸುಮಾರು). ಉದಾಹರಣೆಗೆ, n ನ ಉದ್ದವು ಕೇವಲ 11 ಅಂಕೆಗಳಾಗಿದ್ದರೂ, ಅದಕ್ಕಿಂತ ಸ್ವಲ್ಪ ಕಡಿಮೆ ಸಂಖ್ಯೆಗೆ ಸುಮಾರು 100,000 ವಿಭಾಗಗಳ ಅಗತ್ಯವಿರುತ್ತದೆ. ಇದಲ್ಲದೆ, ಈ ಅಲ್ಗಾರಿದಮ್ ಅಪ್ರಾಯೋಗಿಕವಾದ ಇನ್ಪುಟ್ ಅನ್ನು (ಉದಾಹರಣೆಗೆ, 300-ಅಂಕಿಯ ಸಂಖ್ಯೆ) ಸುಲಭವಾಗಿ ಬರೆಯಬಹುದು. ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯು (ಎನ್ಕೋಡ್ ಮಾಡಲಾದ) ಇನ್ಪುಟ್ನ ಉದ್ದಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ಕಷ್ಟವನ್ನು ಅಳೆಯುವುದರಿಂದ, ಈ ನಿಷ್ಕಪಟ ಅಲ್ಗಾರಿದಮ್ ವಾಸ್ತವವಾಗಿ ಘಾತೀಯವಾಗಿದೆ. ಆದಾಗ್ಯೂ, ಇದು ಹುಸಿ-ಬಹುಪದೀಯ ಸಮಯವಾಗಿದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನಿಜವಾದ ಬಹುಪದೀಯ ಸಂಖ್ಯಾ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ ಹೋಲಿಸಿ-ಉದಾಹರಣೆಗೆ, ಸೇರ್ಪಡೆಗಾಗಿ ನೇರವಾದ ಅಲ್ಗಾರಿದಮ್ಃ ಎರಡು 9-ಅಂಕಿಯ ಸಂಖ್ಯೆಗಳನ್ನು ಸೇರಿಸುವುದು ಸುಮಾರು 9 ಸರಳ ಹಂತಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಮತ್ತು ಸಾಮಾನ್ಯವಾಗಿ ಅಲ್ಗಾರಿದಮ್ ಇನ್ಪುಟ್ನ ಉದ್ದದಲ್ಲಿ ನಿಜವಾಗಿಯೂ ರೇಖೀಯವಾಗಿರುತ್ತದೆ. ಸೇರಿಸಲಾಗುತ್ತಿರುವ ನಿಜವಾದ ಸಂಖ್ಯೆಗಳಿಗೆ ಹೋಲಿಸಿದರೆ (ಶತಕೋಟಿಗಳಲ್ಲಿ), ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು "ಸೂಡೋ-ಲಾಗರಿಥಮಿಕ್ ಟೈಮ್" ಎಂದು ಕರೆಯಬಹುದು, ಆದರೂ ಅಂತಹ ಪದವು ಪ್ರಮಾಣಿತವಾಗಿಲ್ಲ. ಹೀಗಾಗಿ, 300-ಅಂಕಿಯ ಸಂಖ್ಯೆಗಳನ್ನು ಸೇರಿಸುವುದು ಅಪ್ರಾಯೋಗಿಕವಲ್ಲ. ಅಂತೆಯೇ, ದೀರ್ಘ ವಿಭಜನೆಯು ಚತುರ್ಭುಜವಾಗಿದೆಃ ಒಂದು m-ಅಂಕಿಯ ಸಂಖ್ಯೆಯನ್ನು n-ಅಂಕಿಯ ಸಂಖ್ಯೆಯಿಂದ ಹಂತಗಳಲ್ಲಿ ಭಾಗಿಸಬಹುದು (ಬಿಗ್ O ಸಂಕೇತವನ್ನು ನೋಡಿ.) ಪ್ರಾಥಮಿಕತೆಯ ಸಂದರ್ಭದಲ್ಲಿ, ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಚಲಿಸುವ n ಅವಿಭಾಜ್ಯವಾಗಿದೆಯೇ (2002ರಲ್ಲಿ ಪತ್ತೆಯಾಗಿದೆ) ಎಂಬುದನ್ನು ಪರೀಕ್ಷಿಸಲು ಬೇರೆ ಅಲ್ಗಾರಿದಮ್ ಇದೆ. ನಾಪ್ಸ್ಯಾಕ್ ಸಮಸ್ಯೆಯು ನಾಪ್ಸ್ಯಾಕ್ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ತೂಕ ಮತ್ತು ಮೌಲ್ಯದ ವಸ್ತುಗಳನ್ನು ನೀಡಲಾಗುತ್ತದೆ, ಜೊತೆಗೆ ನಾಪ್ಸ್ಯಾಕ್ನ ಗರಿಷ್ಠ ತೂಕದ ಸಾಮರ್ಥ್ಯವನ್ನು ನೀಡಲಾಗುತ್ತದೆ. ಈ ಕೆಳಗಿನ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವುದು ಗುರಿಯಾಗಿದೆ; ಅನೌಪಚಾರಿಕವಾಗಿ, ಮೌಲ್ಯವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಲು ವಸ್ತುಗಳನ್ನು ನಾಪ್ಸ್ಯಾಕ್ನಲ್ಲಿ ಹೊಂದಿಸಲು ಉತ್ತಮ ಮಾರ್ಗ ಯಾವುದು? ಮತ್ತು ಗೆ ಒಳಪಟ್ಟು ಗರಿಷ್ಠಗೊಳಿಸಿ. ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವುದು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿದೆ, ಆದ್ದರಿಂದ ಬಹುಪದ ಸಮಯದ ಕ್ರಮಾವಳಿ ಅಸಾಧ್ಯವಾಗಿದೆ. ಆದಾಗ್ಯೂ, ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ ಸಾಧ್ಯವಿದೆ; ಸಂಖ್ಯೆಯನ್ನು ವಿವರಿಸಲು ಬಿಟ್ಗಳು ಮಾತ್ರ ಬೇಕಾಗಿರುವುದರಿಂದ, ಈ ಅಲ್ಗಾರಿದಮ್ ಹುಸಿ-ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಸೂಡೊ-ಪಾಲಿನೋಮಿಯಲ್ ಸಮಯದ ಕಲ್ಪನೆಯನ್ನು ಬಹುತೇಕ ಪ್ರತ್ಯೇಕವಾಗಿ ಸಂಖ್ಯಾ ಸಮಸ್ಯೆಗಳಿಗೆ ಬಳಸಲಾಗಿದ್ದರೂ, ಈ ಪರಿಕಲ್ಪನೆಯನ್ನು ಸಾಮಾನ್ಯೀಕರಿಸಬಹುದುಃ m (n) ಸಮಸ್ಯೆಯ ಗಾತ್ರ n ರ ಬಹುಪದ ಕಾರ್ಯಕ್ಕಿಂತ ದೊಡ್ಡದಲ್ಲದಿದ್ದರೆ ಮತ್ತು ಇನ್ಪುಟ್ನ ಹೆಚ್ಚುವರಿ ಗುಣಲಕ್ಷಣವಾದ k (n) ಆಗಿದ್ದರೆ m ಕಾರ್ಯವು ಸೂಡೊ-ಪಾಲಿನೋಮಿಯಲ್ ಆಗಿದೆ. (ಸಂಭಾವ್ಯವಾಗಿ, k ಅನ್ನು ಸಮಸ್ಯೆಗೆ ಸೂಕ್ತವಾದದ್ದೆಂದು ಆಯ್ಕೆ ಮಾಡಲಾಗಿದೆ.) ಇದು k ಅನ್ನು ಇನ್ಪುಟ್ನ ಸಂಖ್ಯಾ ಮೌಲ್ಯವಾಗಿ ತೆಗೆದುಕೊಳ್ಳುವ ಮೂಲಕ ಸಂಖ್ಯಾತ್ಮಕ ಬಹುಪದ ಸಮಸ್ಯೆಗಳನ್ನು ವಿಶೇಷ ಪ್ರಕರಣವನ್ನಾಗಿ ಮಾಡುತ್ತದೆ. ಒಂದು ಸಂಖ್ಯೆಯ ಮೌಲ್ಯ ಮತ್ತು ಅದರ ಉದ್ದದ ನಡುವಿನ ವ್ಯತ್ಯಾಸವು ಎನ್ಕೋಡಿಂಗ್ನಲ್ಲಿದೆಃ ಸಂಖ್ಯಾತ್ಮಕ ಇನ್ಪುಟ್ಗಳನ್ನು ಯಾವಾಗಲೂ ಯುನಾರಿಯಲ್ಲಿ ಎನ್ಕೋಡ್ ಮಾಡಿದರೆ, ಸೂಡೋ-ಬಹುಪದವು ಬಹುಪದದೊಂದಿಗೆ ಹೊಂದಿಕೆಯಾಗುತ್ತದೆ. ಸ್ಟ್ರಾಂಗ್ಲಿ ಎನ್. ಪಿ.-ಕಂಪ್ಲೀಟ್ ಕ್ವಾಸಿ-ಪಾಲಿನೋಮಿಯಲ್ ಟೈಮ್ ರೆಫರೆನ್ಸಸ್ ಅನಾಲಿಸಿಸ್ ಆಫ್ ಅಲ್ಗಾರಿದಮ್ ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಕ್ಲಾಸ್ಸ್ ಕಂಪ್ಯೂಟೇಶನಲ್ ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಥಿಯರಿ ಸ್ಯೂಡೋ-ಪಾಲಿನೋಮಿಯಲ್ ಟೈಮ್ ಅಲ್ಗಾರಿದಮ್ಗಳನ್ನು ಸಹ ನೋಡಿ.