NP-equivalent
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಸಂಕೀರ್ಣತೆ ವರ್ಗ ಎನ್. ಪಿ.-ಸಮಾನತೆಯು ಎನ್. ಪಿ.-ಸುಲಭ ಮತ್ತು ಎನ್. ಪಿ.-ಕಠಿಣವಾದ ಕಾರ್ಯ ಸಮಸ್ಯೆಗಳ ಗುಂಪಾಗಿದೆ. ಎನ್ಪಿ-ಸಮಾನತೆಯು ಕಾರ್ಯದ ಸಮಸ್ಯೆಗಳಿಗೆ ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ನ ಸಾದೃಶ್ಯವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, FIND-ಎಸ್ಯುಬಿಎಸ್ಇಟಿ-ಎಸ್ಯುಎಂ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಸಮಾನವಾಗಿರುತ್ತದೆ. ಪೂರ್ಣಾಂಕಗಳ ಗುಂಪನ್ನು ನೀಡಿದರೆ, FIND-SUVSET-SUV ಎಂಬುದು ಶೂನ್ಯಕ್ಕೆ ಸೇರಿಸುವ ಪೂರ್ಣಾಂಕಗಳ ಕೆಲವು ಖಾಲಿ ಇಲ್ಲದ ಉಪಗುಂಪನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆಯಾಗಿದೆ (ಅಥವಾ ಅಂತಹ ಉಪಗುಂಪು ಇಲ್ಲದಿದ್ದರೆ ಖಾಲಿ ಗುಂಪನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ). ಈ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯು ಸಬ್ ಸೆಟ್-ಎಸ್ಯುಎಂ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯನ್ನು ಹೋಲುತ್ತದೆ. ಪೂರ್ಣಾಂಕಗಳ ಗುಂಪನ್ನು ನೀಡಿದರೆ, ಸಬ್ ಸೆಟ್-ಎಸ್ಯುಎಂ ಎಂಬುದು ಶೂನ್ಯಕ್ಕೆ ಒಟ್ಟುಗೂಡಿಸುವ ಉಪವಿಭಾಗವಿದೆಯೇ ಎಂದು ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಸಬ್ ಸೆಟ್-ಎಸ್ಯುಎಂ ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ. ಎಫ್. ಐ. ಎನ್. ಡಿ.-ಎಸ್. ಯು. ಬಿ. ಎಸ್. ಇ. ಟಿ.-ಎಸ್. ಯು. ಎಂ. ಎನ್. ಪಿ. ಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಎಂದು ತೋರಿಸಲು, ಅದು ಎನ್. ಪಿ.-ಕಠಿಣ ಮತ್ತು ಎನ್. ಪಿ.-ಸುಲಭ ಎಂದು ನಾವು ತೋರಿಸಬೇಕು. ಸ್ಪಷ್ಟವಾಗಿ ಇದು ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ. ನಮ್ಮಲ್ಲಿ FIND-ಸಬ್ ಸೆಟ್-ಎಸ್ಯುಎಂ ಅನ್ನು ಯುನಿಟ್ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸುವ ಕಪ್ಪು ಪೆಟ್ಟಿಗೆ ಇದ್ದರೆ, ಸಬ್ ಸೆಟ್-ಎಸ್ಯುಎಂ ಅನ್ನು ಪರಿಹರಿಸುವುದು ಸುಲಭವಾಗುತ್ತದೆ. ಶೂನ್ಯಕ್ಕೆ ಒಟ್ಟುಗೂಡಿಸುವ ಉಪಗುಂಪನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕಪ್ಪು ಪೆಟ್ಟಿಗೆಯನ್ನು ಕೇಳಿ, ನಂತರ ಅದು ಖಾಲಿ ಇಲ್ಲದ ಸೆಟ್ ಅನ್ನು ಹಿಂದಿರುಗಿಸಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ. ಇದು ಎನ್ಪಿ-ಸುಲಭವೂ ಆಗಿದೆ. ನಮ್ಮಲ್ಲಿ ಸಬ್ ಸೆಟ್-ಎಸ್ಯುಎಂ ಅನ್ನು ಯುನಿಟ್ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸುವ ಕಪ್ಪು ಪೆಟ್ಟಿಗೆ ಇದ್ದರೆ, ನಾವು ಅದನ್ನು FIND-ಸಬ್ ಸೆಟ್-ಎಸ್ಯುಎಂ ಅನ್ನು ಪರಿಹರಿಸಲು ಬಳಸಬಹುದು. ಅದು ತಪ್ಪಾಗಿ ಹಿಂತಿರುಗಿದರೆ, ನಾವು ತಕ್ಷಣವೇ ಖಾಲಿ ಸೆಟ್ ಅನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ. ಇಲ್ಲದಿದ್ದರೆ, ನಾವು ಪ್ರತಿ ಅಂಶವನ್ನು ಕ್ರಮವಾಗಿ ಭೇಟಿ ಮಾಡಿ ಅದನ್ನು ತೆಗೆದುಹಾಕುತ್ತೇವೆ, ಆದರೆ ನಾವು ಅದನ್ನು ತೆಗೆದುಹಾಕಿದ ನಂತರವೂ ಸಬ್ ಸೆಟ್-ಎಸ್ಯುಎಂ ನಿಜವಾಗಿ ಹಿಂತಿರುಗುತ್ತದೆ. ಒಮ್ಮೆ ನಾವು ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ಭೇಟಿ ನೀಡಿದ ನಂತರ, ಉತ್ತರವನ್ನು ನಿಜದಿಂದ ಸುಳ್ಳು ಎಂದು ಬದಲಾಯಿಸದೆ ಯಾವುದೇ ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕಲು ನಮಗೆ ಸಾಧ್ಯವಾಗುವುದಿಲ್ಲ; ಈ ಹಂತದಲ್ಲಿ ಮೂಲ ಅಂಶಗಳ ಉಳಿದ ಉಪವಿಭಾಗವು ಶೂನ್ಯಕ್ಕೆ ಒಟ್ಟುಗೂಡಬೇಕು. ಅಂಶಗಳ ನಂತರದ ತೆಗೆದುಹಾಕುವಿಕೆಯು ಹಿಂದಿನ ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕುವುದರಿಂದ ಉತ್ತರವನ್ನು ನಿಜದಿಂದ ಸುಳ್ಳುಗೆ ಬದಲಾಯಿಸುತ್ತದೆ ಎಂಬ ಅಂಶವನ್ನು ಬದಲಾಯಿಸುವುದಿಲ್ಲ ಎಂಬುದನ್ನು ನಾವು ಗಮನಿಸಬೇಕು. ಸೂಡೊಕೋಡ್ನಲ್ಲಿಃ ಫಂಕ್ಷನ್ FIND-SABSET-SAM (ಸೆಟ್ S) ಇಲ್ಲದಿದ್ದರೆ (SABSET-SAM (S)), SABSET-SAM (S-{x}) S: = S-{x} ರಿಟರ್ನ್ S ಆಗಿದ್ದರೆ, S ನಲ್ಲಿನ ಪ್ರತಿ x ಗೆ {} ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ಸ್ಪಷ್ಟೀಕರಣ ಈ ಸಂದರ್ಭದಲ್ಲಿ ಎನ್. ಪಿ. ಯು ಅನಿರ್ಧಾರಣೀಯ ಬಹುಪದ ಸಮಯವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಬೂಲಿಯನ್ ಕಾರ್ಯಗಳ ಎನ್. ಪಿ.-ಸಮಾನತೆಯ ವರ್ಗಗಳೂ ಇವೆ, ಅಲ್ಲಿ ಎನ್. ಪಿ. ಎಂದರೆ ನಿರಾಕರಣೆ ಮತ್ತು ಕ್ರಮಪಲ್ಲಟನೆ. ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳು. ಸಂಕೀರ್ಣತೆ ತರಗತಿಗಳು