Co-NP-complete
ಸಂಕೀರ್ಣತೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಸಹ-ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿರುವ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಮಸ್ಯೆಗಳು ಸಹ-ಎನ್. ಪಿ. ಯಲ್ಲಿ ಕಠಿಣವಾದ ಸಮಸ್ಯೆಗಳಾಗಿವೆ, ಅಂದರೆ ಸಹ-ಎನ್. ಪಿ. ಯಲ್ಲಿನ ಯಾವುದೇ ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದೀಯ ಓವರ್ಹೆಡ್ನೊಂದಿಗೆ ಯಾವುದೇ ಸಹ-ಎನ್. ಪಿ.-ಪೂರ್ಣ ಸಮಸ್ಯೆಯ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿ ಮರುರೂಪಿಸಬಹುದು. ಪಿ ಸಹ-ಎನ್. ಪಿ. ಗಿಂತ ಭಿನ್ನವಾಗಿದ್ದರೆ, ಎಲ್ಲಾ ಸಹ-ಎನ್. ಪಿ.-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಲಾಗುವುದಿಲ್ಲ. ಕೋ-ಎನ್. ಪಿ.-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಯನ್ನು ತ್ವರಿತವಾಗಿ ಪರಿಹರಿಸಲು ಒಂದು ಮಾರ್ಗವಿದ್ದರೆ, ಆ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಎಲ್ಲಾ ಕೋ-ಎನ್. ಪಿ. ಸಮಸ್ಯೆಗಳನ್ನು ತ್ವರಿತವಾಗಿ ಪರಿಹರಿಸಲು ಬಳಸಬಹುದು. ಪ್ರತಿ ಸಹ-ಎನ್. ಪಿ.-ಪೂರ್ಣ ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ.-ಪೂರ್ಣ ಸಮಸ್ಯೆಯ ಪೂರಕವಾಗಿದೆ. ಎನ್ಪಿ ಮತ್ತು ಕೋ-ಎನ್ಪಿ ಎರಡರಲ್ಲೂ ಕೆಲವು ಸಮಸ್ಯೆಗಳಿವೆ, ಉದಾಹರಣೆಗೆ ಪಿ ಅಥವಾ ಪೂರ್ಣಾಂಕ ಅಪವರ್ತನೀಕರಣದಲ್ಲಿನ ಎಲ್ಲಾ ಸಮಸ್ಯೆಗಳು. ಆದಾಗ್ಯೂ, ಸೆಟ್ಗಳು ಸಮಾನವಾಗಿವೆಯೇ ಎಂಬುದು ತಿಳಿದಿಲ್ಲ, ಆದಾಗ್ಯೂ ಅಸಮಾನತೆಯ ಸಾಧ್ಯತೆ ಹೆಚ್ಚು ಎಂದು ಭಾವಿಸಲಾಗಿದೆ. ಹೆಚ್ಚಿನ ವಿವರಗಳಿಗಾಗಿ ಕೋ-ಎನ್ಪಿ ಮತ್ತು ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಅನ್ನು ನೋಡಿ. ಯಾವುದೇ ವಿರಳ ಭಾಷೆಯು ಸಹ-ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿದ್ದರೆ (ಅಥವಾ ಕೇವಲ ಸಹ-ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದ್ದರೆ), ಅದು ಮಹಾನಿಯ ಪ್ರಮೇಯಕ್ಕೆ ನಿರ್ಣಾಯಕ ಅಡಿಪಾಯವಾಗಿದೆ ಎಂದು ಫಾರ್ಚೂನ್ 1979ರಲ್ಲಿ ತೋರಿಸಿತು. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನ ಸಿ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯು ಸಹ-ಎನ್. ಪಿ. ಯಲ್ಲಿದ್ದರೆ ಮತ್ತು ಸಹ-ಎನ್. ಪಿ. ಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆಯು ಬಹುಪದ-ಸಮಯ ಅನೇಕ-ಒಂದನ್ನು ಕಡಿಮೆಗೊಳಿಸಬಹುದಾದರೆ ಅದು ಸಹ-ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿರುತ್ತದೆ. ಇದರರ್ಥ ಪ್ರತಿ ಕೋ-ಎನ್. ಪಿ. ಸಮಸ್ಯೆ ಎಲ್ ಗೆ, ಬಹುಪದ ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ, ಇದು ಎಲ್ ನ ಯಾವುದೇ ನಿದರ್ಶನವನ್ನು ಅದೇ ಸತ್ಯ ಮೌಲ್ಯದೊಂದಿಗೆ ಸಿ ಯ ನಿದರ್ಶನವಾಗಿ ಪರಿವರ್ತಿಸಬಹುದು. ಇದರ ಪರಿಣಾಮವಾಗಿ, ನಾವು C ಗಾಗಿ ಬಹುಪದ ಸಮಯದ ಕ್ರಮಾವಳಿಯನ್ನು ಹೊಂದಿದ್ದರೆ, ನಾವು ಎಲ್ಲಾ ಸಹ-NP ಸಮಸ್ಯೆಗಳನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಉದಾಹರಣೆ ಕೋ-ಎನ್. ಪಿ.-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಯ ಒಂದು ಉದಾಹರಣೆಯೆಂದರೆ ಟಾಟಾಲಜಿ, ಇದು ನೀಡಲಾದ ಬೂಲಿಯನ್ ಸೂತ್ರವು ಟಾಟಾಲಜಿ ಆಗಿದೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವ ಸಮಸ್ಯೆಯಾಗಿದೆ; ಅಂದರೆ, ಚರರಾಶಿಗಳಿಗೆ ನಿಜವಾದ/ಸುಳ್ಳು ಮೌಲ್ಯಗಳ ಪ್ರತಿಯೊಂದು ಸಂಭಾವ್ಯ ನಿಯೋಜನೆಯು ನಿಜವಾದ ಹೇಳಿಕೆಯನ್ನು ನೀಡುತ್ತದೆಯೇ. ಇದು ಬೂಲಿಯನ್ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಯೊಂದಿಗೆ ನಿಕಟ ಸಂಬಂಧವನ್ನು ಹೊಂದಿದೆ, ಇದು ಅಂತಹ ಕನಿಷ್ಠ ಒಂದು ನಿಯೋಜನೆ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆಯೇ ಮತ್ತು ಎನ್. ಪಿ-ಪೂರ್ಣವಾಗಿದೆಯೇ ಎಂದು ಕೇಳುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಸಂಕೀರ್ಣತೆ ವರ್ಗಗಳು