NP-hardness
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಎನ್. ಪಿ.-ಗಡಸುತನವು (ನಿರ್ಣಾಯಕವಲ್ಲದ ಬಹುಪದ-ಸಮಯದ ಗಡಸುತನ) ಅನೌಪಚಾರಿಕವಾಗಿ "ಕನಿಷ್ಠ ಎನ್. ಪಿ. ಯಲ್ಲಿನ ಕಠಿಣ ಸಮಸ್ಯೆಗಳಷ್ಟೇ ಕಠಿಣವಾದ" ಸಮಸ್ಯೆಗಳ ಒಂದು ವರ್ಗದ ವ್ಯಾಖ್ಯಾನಿಸುವ ಗುಣವಾಗಿದೆ. ಎನ್ಪಿ-ಹಾರ್ಡ್ ಸಮಸ್ಯೆಯ ಒಂದು ಸರಳ ಉದಾಹರಣೆಯೆಂದರೆ ಉಪಗುಂಪು ಮೊತ್ತದ ಸಮಸ್ಯೆ. ಹೆಚ್ಚು ನಿಖರವಾದ ವಿವರಣೆಯೆಂದರೆಃ ಎನ್. ಪಿ. ಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆ ಎಲ್ ಅನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಎಚ್ ಗೆ ಕಡಿಮೆ ಮಾಡಿದಾಗ ಸಮಸ್ಯೆ ಎಚ್ ಎನ್. ಪಿ-ಕಠಿಣವಾಗಿದೆ; ಅಂದರೆ, ಎಚ್ ಗೆ ಪರಿಹಾರವು 1 ಯುನಿಟ್ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಎಂದು ಭಾವಿಸಿದರೆ, ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಎಲ್ ಅನ್ನು ಪರಿಹರಿಸಲು ಎಚ್ಎಸ್ ಪರಿಹಾರವನ್ನು ಬಳಸಬಹುದು. ಇದರ ಪರಿಣಾಮವಾಗಿ, ಯಾವುದೇ ಎನ್. ಪಿ.-ಹಾರ್ಡ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಬಹುಪದ ಸಮಯದ ಕ್ರಮಾವಳಿಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಎನ್. ಪಿ. ಯಲ್ಲಿನ ಎಲ್ಲಾ ಸಮಸ್ಯೆಗಳಿಗೆ ಬಹುಪದ ಸಮಯ ಕ್ರಮಾವಳಿಗಳನ್ನು ನೀಡುತ್ತದೆ. ಪಿ ಷ್ಣ ಎನ್ಪಿ ಎಂದು ಶಂಕಿಸಲಾಗಿರುವುದರಿಂದ, ಅಂತಹ ಅಲ್ಗಾರಿದಮ್ ಅಸ್ತಿತ್ವದಲ್ಲಿರುವುದು ಅಸಂಭವವಾಗಿದೆ. ಎನ್ಪಿ-ಹಾರ್ಡ್ ಸಮಸ್ಯೆಗಳಿಗೆ ಯಾವುದೇ ಬಹುಪದ-ಸಮಯದ ಕ್ರಮಾವಳಿಗಳಿಲ್ಲ ಎಂದು ಶಂಕಿಸಲಾಗಿದೆ, ಆದರೆ ಅದು ಸಾಬೀತಾಗಿಲ್ಲ. ಇದಲ್ಲದೆ, ಎಲ್ಲಾ ಸಮಸ್ಯೆಗಳನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದಾದ ಪಿ ವರ್ಗವು ಎನ್. ಪಿ ವರ್ಗದಲ್ಲಿದೆ. ವ್ಯಾಖ್ಯಾನಃ ಒಂದು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆ H ಎಂಬುದು NP-ಕಠಿಣವಾಗಿದ್ದು, NPಯಲ್ಲಿನ ಪ್ರತಿ ಸಮಸ್ಯೆ Lಗೆ, Lನಿಂದ Hಗೆ ಬಹುಪದ-ಸಮಯದ ಅನೇಕ-ಒಂದು ಕಡಿತವಿರುತ್ತದೆ. ಒಂದು ಸಮಾನವಾದ ವ್ಯಾಖ್ಯಾನವೆಂದರೆ NPಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆ L ಅನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ Oracle ಯಂತ್ರದಿಂದ Hಗೆ Oracleನೊಂದಿಗೆ ಪರಿಹರಿಸಬಹುದು. ಅನೌಪಚಾರಿಕವಾಗಿ, ಅಂತಹ Oracle ಯಂತ್ರವನ್ನು H ಅನ್ನು ಪರಿಹರಿಸಲು ಸಬ್ ರುಟೀನ್ ಎಂದು ಕರೆಯುವ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಯೋಚಿಸಬಹುದು ಮತ್ತು ಸಬ್ ರುಟೀನ್ ಕರೆ ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಕೇವಲ ಒಂದು ಹೆಜ್ಜೆ ತೆಗೆದುಕೊಂಡರೆ L ಅನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸುತ್ತದೆ. ಮತ್ತೊಂದು ವ್ಯಾಖ್ಯಾನವೆಂದರೆ ಎನ್ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಯಾದ ಜಿ ಯಿಂದ ಎಚ್ ಗೆ ಬಹುಪದ-ಸಮಯದ ಕಡಿತವು ಅಗತ್ಯವಾಗಿರುತ್ತದೆ. ಎನ್ಪಿಯಲ್ಲಿನ ಯಾವುದೇ ಸಮಸ್ಯೆ ಎಲ್ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಜಿ ಗೆ ಕಡಿಮೆಯಾಗುವುದರಿಂದ, ಎಲ್ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಎಚ್ ಗೆ ಕಡಿಮೆಯಾಗುತ್ತದೆ ಆದ್ದರಿಂದ ಈ ಹೊಸ ವ್ಯಾಖ್ಯಾನವು ಹಿಂದಿನದನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಇದು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳಿಗೆ ವರ್ಗ ಎನ್ಪಿ-ಹಾರ್ಡ್ ಅನ್ನು ನಿರ್ಬಂಧಿಸುವುದಿಲ್ಲ, ಮತ್ತು ಇದು ಹುಡುಕಾಟ ಸಮಸ್ಯೆಗಳು ಅಥವಾ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳನ್ನು ಸಹ ಒಳಗೊಂಡಿದೆ. ಪರಿಣಾಮಗಳು ಪಿ ಷ್ಣುವು ಎನ್. ಪಿ. ಆಗಿದ್ದರೆ, ಎನ್. ಪಿ-ಹಾರ್ಡ್ ಸಮಸ್ಯೆಗಳನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಲು ಸಾಧ್ಯವಾಗುವುದಿಲ್ಲ. ಕೆಲವು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳು ಬಹುಪದ-ಸಮಯದ ಅಂದಾಜು ಕೆಲವು ಸ್ಥಿರ ಅಂದಾಜು ಅನುಪಾತದವರೆಗೆ (ನಿರ್ದಿಷ್ಟವಾಗಿ, ಎಪಿಎಕ್ಸ್ನಲ್ಲಿರುವವು) ಅಥವಾ ಯಾವುದೇ ಅಂದಾಜು ಅನುಪಾತದವರೆಗೆ (ಪಿಟಿಎಎಸ್ ಅಥವಾ ಎಫ್ಪಿಟಿಎಎಸ್ನಲ್ಲಿರುವವು) ಆಗಿರಬಹುದು. ಉದಾಹರಣೆಗಳು ಎಲ್ಲಾ ಎನ್ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳು ಸಹ ಎನ್ಪಿ-ಕಠಿಣವಾಗಿವೆ (ಎನ್ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳ ಪಟ್ಟಿಯನ್ನು ನೋಡಿ). ಉದಾಹರಣೆಗೆ, ಸಾಮಾನ್ಯವಾಗಿ ಟ್ರಾವೆಲಿಂಗ್ ಸೇಲ್ಸ್ಮ್ಯಾನ್ ಪ್ರಾಬ್ಲಮ್ ಎಂದು ಕರೆಯಲಾಗುವ ತೂಕದ ಗ್ರಾಫ್ನ ಎಲ್ಲಾ ನೋಡ್ಗಳ ಮೂಲಕ ಕಡಿಮೆ ವೆಚ್ಚದ ಆವರ್ತಕ ಮಾರ್ಗವನ್ನು ಕಂಡುಹಿಡಿಯುವ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಆಗಿದೆ. ಉಪಗುಂಪು ಮೊತ್ತದ ಸಮಸ್ಯೆಯು ಮತ್ತೊಂದು ಉದಾಹರಣೆಯಾಗಿದೆಃ ಪೂರ್ಣಾಂಕಗಳ ಗುಂಪನ್ನು ನೀಡಿದರೆ, ಅವುಗಳಲ್ಲಿ ಯಾವುದೇ ಖಾಲಿ-ಅಲ್ಲದ ಉಪಗುಂಪುಗಳು ಶೂನ್ಯಕ್ಕೆ ಸೇರುತ್ತವೆಯೇ? ಅದು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯಾಗಿದೆ ಮತ್ತು ಎನ್. ಪಿ.-ಸಂಪೂರ್ಣವಾಗಿದೆ. ನಿಲುಗಡೆ ಸಮಸ್ಯೆಯಂತಹ ಎನ್ಪಿ-ಕಠಿಣ ಆದರೆ ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿರದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳಿವೆ. ಅದು "ಒಂದು ಪ್ರೋಗ್ರಾಂ ಮತ್ತು ಅದರ ಇನ್ಪುಟ್ ಅನ್ನು ನೀಡಿದರೆ, ಅದು ಶಾಶ್ವತವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆಯೇ?" ಎಂದು ಕೇಳುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಅದು ಹೌದು/ಇಲ್ಲ ಎಂಬ ಪ್ರಶ್ನೆ ಮತ್ತು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯೂ ಆಗಿದೆ. ನಿಲ್ಲಿಸುವ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿದೆ ಆದರೆ ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿಲ್ಲ ಎಂದು ಸಾಬೀತುಪಡಿಸುವುದು ಸುಲಭ. ಉದಾಹರಣೆಗೆ, ಬೂಲಿಯನ್ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಯನ್ನು ಎಲ್ಲಾ ಸತ್ಯ ಮೌಲ್ಯದ ನಿಯೋಜನೆಗಳನ್ನು ಪ್ರಯತ್ನಿಸುವ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದ ವಿವರಣೆಗೆ ಪರಿವರ್ತಿಸುವ ಮೂಲಕ ನಿಲ್ಲಿಸುವ ಸಮಸ್ಯೆಯಾಗಿ ಕಡಿಮೆ ಮಾಡಬಹುದು ಮತ್ತು ಅದು ಸೂತ್ರವನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ಒಂದನ್ನು ಕಂಡುಕೊಂಡಾಗ ಅದು ನಿಲ್ಲುತ್ತದೆ ಮತ್ತು ಇಲ್ಲದಿದ್ದರೆ ಅದು ಅನಂತ ಲೂಪ್ಗೆ ಹೋಗುತ್ತದೆ. ಎನ್. ಪಿ. ಯಲ್ಲಿನ ಎಲ್ಲಾ ಸಮಸ್ಯೆಗಳು ಸೀಮಿತ ಸಂಖ್ಯೆಯ ಕಾರ್ಯಾಚರಣೆಗಳಲ್ಲಿ ನಿರ್ಣಾಯಕವಾಗಿರುವುದರಿಂದ ನಿಲುಗಡೆ ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ. ಯಲ್ಲಿಲ್ಲ ಎಂದು ನೋಡುವುದು ಸಹ ಸುಲಭ, ಆದರೆ ಸಾಮಾನ್ಯವಾಗಿ ನಿಲುಗಡೆ ಸಮಸ್ಯೆಯು ಅನಿಶ್ಚಿತವಾಗಿದೆ. ಎನ್. ಪಿ.-ಕಠಿಣ ಸಮಸ್ಯೆಗಳೂ ಸಹ ಇವೆ, ಅವು ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿಲ್ಲ ಅಥವಾ ನಿರ್ಣಯಿಸಲಾಗುವುದಿಲ್ಲ. ಉದಾಹರಣೆಗೆ, ನಿಜವಾದ ಪರಿಮಾಣಿತ ಬೂಲಿಯನ್ ಸೂತ್ರಗಳ ಭಾಷೆಯು ಬಹುಪದ ಜಾಗದಲ್ಲಿ ನಿರ್ಣಾಯಕವಾಗಿರುತ್ತದೆ, ಆದರೆ ನಿರ್ಣಾಯಕವಲ್ಲದ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಅಲ್ಲ (ಎನ್. ಪಿ. = ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ ಹೊರತು). ಎನ್. ಪಿ.-ನಾಮಕರಣ ಸಂಪ್ರದಾಯ ಎನ್. ಪಿ.-ಕಠಿಣ ಸಮಸ್ಯೆಗಳು ಸಂಕೀರ್ಣತೆಯ ವರ್ಗ ಎನ್. ಪಿ. ಯ ಅಂಶಗಳಾಗಿರಬೇಕಾಗಿಲ್ಲ. ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯಲ್ಲಿ ಎನ್ಪಿ ಪ್ರಮುಖ ಪಾತ್ರ ವಹಿಸುತ್ತದೆಯಾದ್ದರಿಂದ, ಇದನ್ನು ಹಲವಾರು ವರ್ಗಗಳ ಆಧಾರವಾಗಿ ಬಳಸಲಾಗುತ್ತದೆಃ ಕಂಪ್ಯೂಟೇಶನಲ್ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳ ಎನ್ಪಿ ವರ್ಗ, ಇದಕ್ಕಾಗಿ ಯಾವುದೇ ಹೌದು-ಪರಿಹಾರವನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ನಿರ್ಣಾಯಕ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ (ಅಥವಾ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ನಿರ್ಣಾಯಕವಲ್ಲದ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಪರಿಹರಿಸಬಹುದಾದ) ಪರಿಹಾರವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದು. ಎನ್. ಪಿ.-ಕಠಿಣ ವರ್ಗದ ಸಮಸ್ಯೆಗಳು ಕನಿಷ್ಠ ಎನ್. ಪಿ. ಯಲ್ಲಿನ ಕಠಿಣ ಸಮಸ್ಯೆಗಳಷ್ಟೇ ಕಠಿಣವಾಗಿವೆ. ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿರುವ ಸಮಸ್ಯೆಗಳು ಎನ್. ಪಿ. ಯ ಅಂಶಗಳಾಗಿರಬೇಕಾಗಿಲ್ಲ; ವಾಸ್ತವವಾಗಿ, ಅವು ನಿರ್ಣಾಯಕವೂ ಆಗಿರಬಾರದು. ಎನ್. ಪಿ. ಯಲ್ಲಿ ಅತ್ಯಂತ ಕಠಿಣವಾದ ಸಮಸ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳ ಎನ್. ಪಿ.-ಪೂರ್ಣ ವರ್ಗ. ಪ್ರತಿ ಎನ್ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಯು ಎನ್ಪಿಯಲ್ಲಿರಬೇಕು. ಎನ್. ಪಿ.-ಸುಲಭ ಎನ್. ಪಿ. ಯಷ್ಟು ಕಠಿಣವಾಗಿದೆ, ಆದರೆ ಎನ್. ಪಿ. ಯಲ್ಲಿ ಇರಬೇಕಾಗಿಲ್ಲ. ಎನ್ಪಿ-ಸಮಾನ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಮತ್ತು ಎನ್ಪಿ-ಸುಲಭ ಎರಡೂ ಆಗಿರುತ್ತವೆ, ಆದರೆ ಎನ್ಪಿಯಲ್ಲಿ ಇರಬೇಕಾಗಿಲ್ಲ. ಪಿ ಮತ್ತು ಎನ್ಪಿ ಭಿನ್ನವಾಗಿದ್ದರೆ, ಪಿ ಮತ್ತು ಎನ್ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳ ನಡುವೆ ಬರುವ ಎನ್ಪಿ ಪ್ರದೇಶದಲ್ಲಿ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳಿವೆ. (ಪಿ ಮತ್ತು ಎನ್ಪಿ ಒಂದೇ ವರ್ಗವಾಗಿದ್ದರೆ, ಎನ್ಪಿ-ಮಧ್ಯಂತರ ಸಮಸ್ಯೆಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿರುವುದಿಲ್ಲ ಏಕೆಂದರೆ ಈ ಸಂದರ್ಭದಲ್ಲಿ ಪ್ರತಿ ಎನ್ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಯು ಪಿ ಯಲ್ಲಿ ಬರುತ್ತದೆ, ಮತ್ತು ವ್ಯಾಖ್ಯಾನದ ಪ್ರಕಾರ, ಎನ್ಪಿಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆಯನ್ನು ಎನ್ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಯಾಗಿ ಕಡಿಮೆ ಮಾಡಬಹುದು.) ಅಪ್ಲಿಕೇಶನ್ ಕ್ಷೇತ್ರಗಳು ಎನ್. ಪಿ.-ಕಠಿಣ ಸಮಸ್ಯೆಗಳನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ನಿಯಮ-ಆಧಾರಿತ ಭಾಷೆಗಳೊಂದಿಗೆ ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಒಳಗೊಂಡಂತೆ ನಿಭಾಯಿಸಲಾಗುತ್ತದೆಃ ಅಂದಾಜು ಕಂಪ್ಯೂಟಿಂಗ್ ಕಾನ್ಫಿಗರೇಶನ್ ಕ್ರಿಪ್ಟೋಗ್ರಫಿ ಡೇಟಾ ಮೈನಿಂಗ್ ನಿರ್ಧಾರ ಬೆಂಬಲ ಫೈಲೋಜೆನೆಟಿಕ್ಸ್ ಯೋಜನೆ ಪ್ರಕ್ರಿಯೆ ಮೇಲ್ವಿಚಾರಣೆ ಮತ್ತು ನಿಯಂತ್ರಣ ರೋಸ್ಟರ್ಗಳು ಅಥವಾ ವೇಳಾಪಟ್ಟಿಗಳು ರೂಟಿಂಗ್/ವಾಹನ ರೂಟಿಂಗ್ ವೇಳಾಪಟ್ಟಿ ಸಹ ನೋಡಿ ಪರಿಹರಿಸಲಾಗದ ಸಮಸ್ಯೆಗಳ ಪಟ್ಟಿ ಕಡಿತ (ಸಂಕೀರ್ಣತೆ) ಅಜ್ಞಾತತೆ ಉಲ್ಲೇಖಗಳು ಸಂಕೀರ್ಣತೆ ವರ್ಗಗಳು