NP-easy
ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಸಂಕೀರ್ಣತೆ ವರ್ಗ ಎನ್. ಪಿ.-ಸುಲಭವು ಎನ್. ಪಿ. ಯಲ್ಲಿನ ಕೆಲವು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳಿಗೆ ಒರಾಕಲ್ನೊಂದಿಗೆ ನಿರ್ಣಾಯಕ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದಾದ ಕಾರ್ಯ ಸಮಸ್ಯೆಗಳ ಗುಂಪಾಗಿದೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, X ಯು ಬಹುಪದ-ಸಮಯದ ಟ್ಯೂರಿಂಗ್ ಅನ್ನು Y ಗೆ ಕಡಿತಗೊಳಿಸಬಹುದಾದಂತಹ NP ಯಲ್ಲಿ ಕೆಲವು ಸಮಸ್ಯೆ Y ಇದ್ದರೆ ಮಾತ್ರ X ಸಮಸ್ಯೆಯು NP-ಸುಲಭವಾಗಿದೆ. ಇದರರ್ಥ ವೈಗೆ ಒಂದು ಒರಾಕಲ್ ಅನ್ನು ನೀಡಿದರೆ, ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಎಕ್ಸ್ ಅನ್ನು ಪರಿಹರಿಸುವ ಅಲ್ಗಾರಿದಮ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ (ಬಹುಶಃ ಆ ಒರಾಕಲ್ ಅನ್ನು ಪದೇ ಪದೇ ಬಳಸುವುದರ ಮೂಲಕ). ಎನ್. ಪಿ.-ಈಸಿ ಎಂಬುದು ಎಫ್. ಪಿ. ಎನ್. ಪಿ. ಗೆ ಮತ್ತೊಂದು ಹೆಸರಾಗಿದೆ (ಕಾರ್ಯ ಸಮಸ್ಯೆಯ ಲೇಖನವನ್ನು ನೋಡಿ) ಅಥವಾ ಎಫ್. ಡಿ. 2. ಪಿ. ಗೆ (ಬಹುಪದ ಶ್ರೇಣಿವ್ಯವಸ್ಥೆಯ ಲೇಖನವನ್ನು ನೋಡಿ). ಎನ್ಪಿ-ಸುಲಭ ಸಮಸ್ಯೆಯ ಒಂದು ಉದಾಹರಣೆಯೆಂದರೆ ತಂತಿಗಳ ಪಟ್ಟಿಯನ್ನು ವಿಂಗಡಿಸುವ ಸಮಸ್ಯೆ. ನಿರ್ಧಾರದ ಸಮಸ್ಯೆ "ಸ್ಟ್ರಿಂಗ್ ಎ ಸ್ಟ್ರಿಂಗ್ ಬಿ ಗಿಂತ ದೊಡ್ಡದಾಗಿದೆ" ಎನ್. ಪಿ. ಯಲ್ಲಿದೆ. ಕ್ವಿಕ್ಸಾರ್ಟ್ನಂತಹ ಕ್ರಮಾವಳಿಗಳಿವೆ, ಅದು ಹೋಲಿಕೆ ದಿನಚರಿಯ ಪಾಲಿನಾಮಿಯಲ್ ಸಂಖ್ಯೆಯ ಕರೆಗಳನ್ನು ಮಾತ್ರ ಬಳಸಿಕೊಂಡು ಪಟ್ಟಿಯನ್ನು ವಿಂಗಡಿಸಬಹುದು, ಜೊತೆಗೆ ಪಾಲಿನಾಮಿಯಲ್ ಪ್ರಮಾಣದ ಹೆಚ್ಚುವರಿ ಕೆಲಸವನ್ನು ಮಾಡಬಹುದು. ಆದ್ದರಿಂದ, ವಿಂಗಡಣೆಯು ಎನ್. ಪಿ.-ಸುಲಭವಾಗಿದೆ. ಎನ್ಪಿ-ಸುಲಭವಾದ ಹೆಚ್ಚು ಕಷ್ಟಕರವಾದ ಸಮಸ್ಯೆಗಳೂ ಇವೆ. ಉದಾಹರಣೆಗಾಗಿ ಎನ್. ಪಿ.-ಸಮಾನತೆಯನ್ನು ನೋಡಿ. ಎನ್ಪಿ-ಈಸಿ ಎಂಬ ವ್ಯಾಖ್ಯಾನವು ಅನೇಕ-ಒಂದರ ಕಡಿತಕ್ಕಿಂತ ಟ್ಯೂರಿಂಗ್ ಕಡಿತವನ್ನು ಬಳಸುತ್ತದೆ ಏಕೆಂದರೆ ವೈ ಸಮಸ್ಯೆಯ ಉತ್ತರಗಳು ಕೇವಲ ನಿಜ ಅಥವಾ ಸುಳ್ಳು, ಆದರೆ ಎಕ್ಸ್ ಸಮಸ್ಯೆಯ ಉತ್ತರಗಳು ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿರಬಹುದು. ಆದ್ದರಿಂದ, Xನ ಒಂದು ನಿದರ್ಶನವನ್ನು Yನ ಒಂದು ನಿದರ್ಶನಕ್ಕೆ ಅದೇ ಉತ್ತರದೊಂದಿಗೆ ಭಾಷಾಂತರಿಸಲು ಯಾವುದೇ ಸಾಮಾನ್ಯ ಮಾರ್ಗವಿಲ್ಲ. ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳು. ಸಂಕೀರ್ಣತೆ ತರಗತಿಗಳು