Unique games conjecture
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ವಿಶಿಷ್ಟವಾದ ಆಟದ ಊಹೆಯು (ಸಾಮಾನ್ಯವಾಗಿ ಯು. ಜಿ. ಸಿ. ಎಂದು ಉಲ್ಲೇಖಿಸಲಾಗುತ್ತದೆ) 2002ರಲ್ಲಿ ಸುಭಾಷ್ ಖೋಟ್ ಅವರು ಮಾಡಿದ ಒಂದು ಊಹೆಯಾಗಿದೆ. ವಿಶಿಷ್ಟ ಆಟ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಒಂದು ನಿರ್ದಿಷ್ಟ ರೀತಿಯ ಆಟದ ಅಂದಾಜು ಮೌಲ್ಯವನ್ನು ನಿರ್ಧರಿಸುವ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದೆ ಎಂದು ಊಹೆಯು ಪ್ರತಿಪಾದಿಸುತ್ತದೆ. ಇದು ಅಂದಾಜಿನ ಗಡಸುತನದ ಸಿದ್ಧಾಂತದಲ್ಲಿ ವಿಶಾಲವಾದ ಅನ್ವಯಗಳನ್ನು ಹೊಂದಿದೆ. ವಿಶಿಷ್ಟವಾದ ಆಟದ ಊಹೆಯು ನಿಜವಾಗಿದ್ದರೆ ಮತ್ತು ಪಿ § ಎನ್. ಪಿ. ಆಗಿದ್ದರೆ, ಅನೇಕ ಪ್ರಮುಖ ಸಮಸ್ಯೆಗಳಿಗೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ನಿಖರವಾದ ಪರಿಹಾರವನ್ನು ಪಡೆಯುವುದು ಅಸಾಧ್ಯವಾಗಿದೆ (ಪಿ ವರ್ಸಸ್ ಎನ್. ಪಿ. ಸಮಸ್ಯೆಯಿಂದ ಪ್ರತಿಪಾದಿಸಿದಂತೆ), ಆದರೆ ಉತ್ತಮ ಬಹುಪದ-ಸಮಯದ ಅಂದಾಜನ್ನು ಪಡೆಯುವುದು ಅಸಾಧ್ಯವಾಗಿದೆ. ಅಂತಹ ಅಸಮರ್ಪಕ ಫಲಿತಾಂಶವು ಹೊಂದಿರುವ ಸಮಸ್ಯೆಗಳು ನಿರ್ಬಂಧದ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿವೆ, ಇದು ವಿವಿಧ ವಿಭಾಗಗಳಲ್ಲಿ ಬೆಳೆಯುತ್ತದೆ. ಇದು ನಿಜವೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದರ ಬಗ್ಗೆ ಶೈಕ್ಷಣಿಕ ಜಗತ್ತಿನಲ್ಲಿ ಸಮಾನವಾಗಿ ಭಿನ್ನಾಭಿಪ್ರಾಯವಿದೆ ಎಂಬ ಊಹೆಯು ಅಸಾಮಾನ್ಯವಾಗಿದೆ. ಸೂತ್ರೀಕರಣಗಳು ವಿಶಿಷ್ಟ ಆಟದ ಊಹೆಯನ್ನು ಹಲವಾರು ಸಮಾನ ರೀತಿಯಲ್ಲಿ ಹೇಳಬಹುದು. ವಿಶಿಷ್ಟ ಲೇಬಲ್ ಕವರ್ ವಿಶಿಷ್ಟ ಆಟದ ಊಹೆಯ ಈ ಕೆಳಗಿನ ಸೂತ್ರೀಕರಣವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಅಂದಾಜಿನ ಗಡಸುತನದಲ್ಲಿ ಬಳಸಲಾಗುತ್ತದೆ. ಈ ಊಹೆಯು ವಿಶಿಷ್ಟ ನಿರ್ಬಂಧಗಳೊಂದಿಗೆ ಲೇಬಲ್ ಕವರ್ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಈ ಕೆಳಗಿನ ಭರವಸೆಯ ಸಮಸ್ಯೆಯ ಎನ್ಪಿ-ಗಡಸುತನವನ್ನು ಪ್ರತಿಪಾದಿಸುತ್ತದೆ. ಪ್ರತಿ ಅಂಚಿಗೆ, ಎರಡು ಶೃಂಗಗಳ ಮೇಲಿನ ಬಣ್ಣಗಳನ್ನು ಕೆಲವು ನಿರ್ದಿಷ್ಟ ಕ್ರಮಬದ್ಧ ಜೋಡಿಗಳಿಗೆ ಸೀಮಿತಗೊಳಿಸಲಾಗಿದೆ. ವಿಶಿಷ್ಟ ನಿರ್ಬಂಧಗಳು ಎಂದರೆ ಪ್ರತಿ ಅಂಚಿಗೆ ಯಾವುದೇ ಕ್ರಮಬದ್ಧ ಜೋಡಿಗಳು ಒಂದೇ ನೋಡ್ಗೆ ಒಂದೇ ಬಣ್ಣವನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. ಇದರರ್ಥ k ಗಾತ್ರದ ವರ್ಣಮಾಲೆಯ ಮೇಲೆ ವಿಶಿಷ್ಟ ನಿರ್ಬಂಧಗಳನ್ನು ಹೊಂದಿರುವ ಲೇಬಲ್ ಕವರ್ನ ಉದಾಹರಣೆಯನ್ನು πe: [k] → [k] ಕ್ರಮಪಲ್ಲಟನೆಗಳ ಸಂಗ್ರಹದೊಂದಿಗೆ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಆಗಿ ಪ್ರತಿನಿಧಿಸಬಹುದು, ಗ್ರಾಫ್ನ ಪ್ರತಿ ಅಂಚಿಗೆ ಒಂದು. ಲೇಬಲ್ ಕವರ್ ನಿದರ್ಶನಕ್ಕೆ ಒಂದು ನಿಯೋಜನೆಯು G ಯ ಪ್ರತಿಯೊಂದು ಶೃಂಗಕ್ಕೂ [k] = {1,2,. k} ಗುಂಪಿನಲ್ಲಿರುವ ಒಂದು ಮೌಲ್ಯವನ್ನು ನೀಡುತ್ತದೆ, ಇದನ್ನು ಸಾಮಾನ್ಯವಾಗಿ "ಬಣ್ಣಗಳು" ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಅಂತಹ ನಿದರ್ಶನಗಳನ್ನು ಬಲವಾಗಿ ನಿರ್ಬಂಧಿಸಲಾಗಿದೆ ಎಂದರೆ ಶೃಂಗದ ಬಣ್ಣವು ಅದರ ನೆರೆಹೊರೆಯವರ ಬಣ್ಣಗಳನ್ನು ಅನನ್ಯವಾಗಿ ವ್ಯಾಖ್ಯಾನಿಸುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಅದರ ಸಂಪೂರ್ಣ ಸಂಪರ್ಕಿತ ಘಟಕಕ್ಕೆ. ಹೀಗಾಗಿ, ಇನ್ಪುಟ್ ನಿದರ್ಶನವು ಮಾನ್ಯವಾದ ನಿಯೋಜನೆಯನ್ನು ಒಪ್ಪಿಕೊಂಡರೆ, ಅಂತಹ ನಿಯೋಜನೆಯನ್ನು ಒಂದೇ ನೋಡ್ನ ಎಲ್ಲಾ ಬಣ್ಣಗಳ ಮೇಲೆ ಪುನರಾವರ್ತಿಸುವ ಮೂಲಕ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಕಂಡುಹಿಡಿಯಬಹುದು. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಕೊಟ್ಟಿರುವ ನಿದರ್ಶನವು ತೃಪ್ತಿಕರವಾದ ನಿಯೋಜನೆಯನ್ನು ಒಪ್ಪಿಕೊಳ್ಳುತ್ತದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವ ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ವಿಶಿಷ್ಟ ಲೇಬಲ್ ಕವರ್ ನಿದರ್ಶನದ ಮೌಲ್ಯವು ಯಾವುದೇ ನಿಯೋಜನೆಯಿಂದ ತೃಪ್ತಿಪಡಿಸಬಹುದಾದ ನಿರ್ಬಂಧಗಳ ಭಾಗವಾಗಿದೆ. ತೃಪ್ತಿಕರ ನಿದರ್ಶನಗಳಿಗೆ, ಈ ಮೌಲ್ಯವು 1 ಆಗಿದೆ ಮತ್ತು ಅದನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಸುಲಭ. ಮತ್ತೊಂದೆಡೆ, ಅತೃಪ್ತಿಕರ ಆಟದ ಮೌಲ್ಯವನ್ನು ನಿರ್ಧರಿಸುವುದು ತುಂಬಾ ಕಷ್ಟಕರವೆಂದು ತೋರುತ್ತದೆ, ಸರಿಸುಮಾರು ಸಹ. ವಿಶಿಷ್ಟವಾದ ಆಟದ ಊಹೆಯು ಈ ಕಷ್ಟವನ್ನು ಔಪಚಾರಿಕಗೊಳಿಸುತ್ತದೆ. ಹೆಚ್ಚು ಔಪಚಾರಿಕವಾಗಿ, ವಿಶಿಷ್ಟ ನಿರ್ಬಂಧಗಳೊಂದಿಗಿನ (ಸಿ, ಎಸ್)-ಗ್ಯಾಪ್ ಲೇಬಲ್-ಕವರ್ ಸಮಸ್ಯೆಯು ಈ ಕೆಳಗಿನ ಭರವಸೆಯ ಸಮಸ್ಯೆಯಾಗಿದೆ (ಲೈಸ್, ಎಲ್ನೋ): ಲೈಸ್ = {ಜಿಃ ಕೆಲವು ನಿಯೋಜನೆಯು ಜಿ} ಎಲ್ನೋ = {ಜಿ ನಲ್ಲಿನ ನಿರ್ಬಂಧಗಳ ಕನಿಷ್ಠ ಸಿ-ಭಾಗವನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆಃ ಪ್ರತಿ ನಿಯೋಜನೆಯು ಜಿ} ನಲ್ಲಿನ ನಿರ್ಬಂಧಗಳ ಎಸ್-ಭಾಗವನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ, ಅಲ್ಲಿ ಜಿ ವಿಶಿಷ್ಟ ನಿರ್ಬಂಧಗಳೊಂದಿಗೆ ಲೇಬಲ್ ಕವರ್ ಸಮಸ್ಯೆಯ ಒಂದು ಉದಾಹರಣೆಯಾಗಿದೆ. ಪ್ರತಿ ಸಾಕಷ್ಟು ಸಣ್ಣ ಜೋಡಿ ಸ್ಥಿರಾಂಕಗಳಾದ ε, δ> 0 ಗೆ, ಸ್ಥಿರವಾದ k ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ, ಅಂದರೆ (1 − δ, ε)-ಗ್ಯಾಪ್ ಲೇಬಲ್-ಕವರ್ ಸಮಸ್ಯೆಯು k ಗಾತ್ರದ ವರ್ಣಮಾಲೆಯ ಮೇಲೆ ವಿಶಿಷ್ಟ ನಿರ್ಬಂಧಗಳನ್ನು ಹೊಂದಿರುವ NP-ಹಾರ್ಡ್ ಆಗಿದೆ. ಗ್ರಾಫ್ಗಳ ಬದಲಿಗೆ, ಲೇಬಲ್ ಕವರ್ ಸಮಸ್ಯೆಯನ್ನು ರೇಖೀಯ ಸಮೀಕರಣಗಳ ಪರಿಭಾಷೆಯಲ್ಲಿ ರೂಪಿಸಬಹುದು. ಉದಾಹರಣೆಗೆ, ನಾವು ಪೂರ್ಣಾಂಕಗಳ ಮಾಡ್ಯುಲೋ 7ರ ಮೇಲೆ ರೇಖೀಯ ಸಮೀಕರಣಗಳ ವ್ಯವಸ್ಥೆಯನ್ನು ಹೊಂದಿದ್ದೇವೆ ಎಂದು ಭಾವಿಸೋಣಃ ಇದು ವಿಶಿಷ್ಟ ನಿರ್ಬಂಧಗಳೊಂದಿಗೆ ಲೇಬಲ್ ಕವರ್ ಸಮಸ್ಯೆಯ ಒಂದು ಉದಾಹರಣೆಯಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ಮೊದಲ ಸಮೀಕರಣವು ಕ್ರಮಪಲ್ಲಟನೆಗೆ (1,2) ಅನುರೂಪವಾಗಿದೆ, ಅಲ್ಲಿ (1,2) (x1) = 2x2 ಮಾಡ್ಯುಲೋ 7 ಆಗಿದೆ. ಎರಡು-ಪುರಾವೆ ಪುರಾವೆ ವ್ಯವಸ್ಥೆಗಳು ಒಂದು ಅನನ್ಯ ಆಟವು ಎರಡು-ಪುರಾವೆ ಒಂದು-ಸುತ್ತಿನ (2ಪಿ1ಆರ್) ಆಟದ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆ. ಎರಡು-ಪ್ರೊವರ್ಗಳ ಒಂದು-ಸುತ್ತಿನ ಆಟವು ಇಬ್ಬರು ಆಟಗಾರರನ್ನು (ಪ್ರೊವರ್ಗಳು ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ) ಮತ್ತು ರೆಫರಿಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ರೆಫರಿಯು ಪ್ರತಿ ಆಟಗಾರನಿಗೆ ತಿಳಿದಿರುವ ಸಂಭವನೀಯತೆಯ ವಿತರಣೆಯಿಂದ ಪಡೆದ ಪ್ರಶ್ನೆಯನ್ನು ಕಳುಹಿಸುತ್ತಾನೆ ಮತ್ತು ಪ್ರತಿಯೊಬ್ಬ ಆಟಗಾರನೂ ಉತ್ತರವನ್ನು ಕಳುಹಿಸಬೇಕಾಗುತ್ತದೆ. ಉತ್ತರಗಳು ನಿಗದಿತ ಗಾತ್ರದ ಗುಂಪಿನಿಂದ ಬರುತ್ತವೆ. ಆಟಗಾರರಿಗೆ ಕಳುಹಿಸಲಾದ ಪ್ರಶ್ನೆಗಳು ಮತ್ತು ಅವರು ನೀಡಿದ ಉತ್ತರಗಳನ್ನು ಅವಲಂಬಿಸಿರುವ ಒಂದು ಭವಿಷ್ಯವಾಣಿಯು ಆಟವನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸುತ್ತದೆ. ಆಟದ ಸಮಯದಲ್ಲಿ ಪರಸ್ಪರ ಸಂವಹನ ನಡೆಸಲು ಸಾಧ್ಯವಾಗದಿದ್ದರೂ, ಆಟಗಾರರು ಒಂದು ಕಾರ್ಯತಂತ್ರವನ್ನು ಮೊದಲೇ ನಿರ್ಧರಿಸಬಹುದು. ಭವಿಷ್ಯವಾಣಿಯು ಅವರ ಪ್ರಶ್ನೆಗಳು ಮತ್ತು ಅವರ ಉತ್ತರಗಳಿಂದ ತೃಪ್ತಿಯಾದರೆ ಆಟಗಾರರು ಗೆಲ್ಲುತ್ತಾರೆ. ಮೊದಲ ಆಟಗಾರನ ಪ್ರತಿ ಪ್ರಶ್ನೆ ಮತ್ತು ಪ್ರತಿ ಉತ್ತರಕ್ಕೆ, ಎರಡನೇ ಆಟಗಾರನು ನಿಖರವಾಗಿ ಒಂದು ಉತ್ತರವನ್ನು ನೀಡಿದರೆ, ಅದು ಆಟಗಾರರ ಗೆಲುವಿಗೆ ಕಾರಣವಾದರೆ, ಎರಡು-ಪುರಾವೆಗಳ ಒಂದು-ಸುತ್ತಿನ ಆಟವನ್ನು ವಿಶಿಷ್ಟ ಆಟ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಆಟದ ಮೌಲ್ಯವು ಎಲ್ಲಾ ತಂತ್ರಗಳ ಮೇಲೆ ಆಟಗಾರರಿಗೆ ಗೆಲ್ಲುವ ಗರಿಷ್ಠ ಸಂಭವನೀಯತೆಯಾಗಿದೆ. ಪ್ರತಿ ಸಾಕಷ್ಟು ಸಣ್ಣ ಜೋಡಿ ಸ್ಥಿರಾಂಕಗಳಾದ ε, δ> 0 ಗೆ, ಈ ಕೆಳಗಿನ ಪ್ರಾಮಿಸ್ ಪ್ರಾಬ್ಲೆಮ್ (ಲೈಸ್, Lno) NP-ಹಾರ್ಡ್ ಆಗಿರುವಂತಹ ಸ್ಥಿರ k ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ ಎಂದು ವಿಶಿಷ್ಟ ಆಟಗಳ ಊಹೆಯು ಹೇಳುತ್ತದೆಃ ಲೈಸ್ = {G: G ಯ ಮೌಲ್ಯವು ಕನಿಷ್ಠ 1 − δ} Lno = {G: G ಯ ಮೌಲ್ಯವು ಗರಿಷ್ಠ ε} ಆಗಿರುತ್ತದೆ, ಅಲ್ಲಿ G ಒಂದು ವಿಶಿಷ್ಟ ಆಟವಾಗಿದ್ದು, ಅದರ ಉತ್ತರಗಳು k ಗಾತ್ರದ ಗುಂಪಿನಿಂದ ಬರುತ್ತವೆ. ಪ್ರಾಯಶಃ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆಗಳು ಪರ್ಯಾಯವಾಗಿ, ಅನನ್ಯ ಆಟಗಳ ಊಹೆಯು NP ಯಲ್ಲಿನ ಸಮಸ್ಯೆಗಳಿಗೆ ಒಂದು ನಿರ್ದಿಷ್ಟ ರೀತಿಯ ಸಂಭವನೀಯವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆಗಳ ಅಸ್ತಿತ್ವವನ್ನು ಪ್ರತಿಪಾದಿಸುತ್ತದೆ. ಒಂದು ವಿಶಿಷ್ಟ ಆಟವನ್ನು ಪ್ರಶ್ನೆಯ ಸಂಕೀರ್ಣತೆ 2 ರೊಂದಿಗೆ ವಿಶೇಷ ರೀತಿಯ ಹೊಂದಾಣಿಕೆಯಾಗದ ಸಂಭವನೀಯವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆಯಾಗಿ ನೋಡಬಹುದು, ಅಲ್ಲಿ ಪರಿಶೀಲಕರ ಪ್ರತಿಯೊಂದು ಜೋಡಿ ಸಂಭವನೀಯ ಪ್ರಶ್ನೆಗಳಿಗೆ ಮತ್ತು ಮೊದಲ ಪ್ರಶ್ನೆಗೆ ಪ್ರತಿ ಸಂಭವನೀಯ ಉತ್ತರಕ್ಕೆ, ಎರಡನೇ ಪ್ರಶ್ನೆಗೆ ನಿಖರವಾಗಿ ಒಂದು ಸಂಭವನೀಯ ಉತ್ತರವಿದೆ. ಪ್ರತಿ ಸಾಕಷ್ಟು ಸಣ್ಣ ಜೋಡಿ ಸ್ಥಿರಾಂಕಗಳಿಗೆ, ಎನ್. ಪಿ. ಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆಯು ಸಂಪೂರ್ಣತೆ, ದೃಢತೆ ಮತ್ತು ಯಾದೃಚ್ಛಿಕ ಸಂಕೀರ್ಣತೆಯೊಂದಿಗೆ ಗಾತ್ರದ ವರ್ಣಮಾಲೆಯ ಮೇಲೆ ಸಂಭವನೀಯವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಇದು ಒಂದು ವಿಶಿಷ್ಟವಾದ ಆಟವಾಗಿದೆ ಎಂದು ವಿಶಿಷ್ಟ ಆಟದ ಊಹೆಯು ಹೇಳುತ್ತದೆ. ಪ್ರಸ್ತುತತೆ ವಿಶಿಷ್ಟವಾದ ಆಟದ ಊಹೆಯನ್ನು 2002 ರಲ್ಲಿ ಸುಭಾಷ್ ಖೋಟ್ ಅವರು ಅಂದಾಜು ಕಠಿಣತೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಕೆಲವು ಪ್ರಶ್ನೆಗಳ ಮೇಲೆ ಪ್ರಗತಿ ಸಾಧಿಸುವ ಸಲುವಾಗಿ ಪರಿಚಯಿಸಿದರು. ವಿಶಿಷ್ಟವಾದ ಆಟದ ಊಹೆಯ ಸತ್ಯವು ಅನೇಕ ತಿಳಿದಿರುವ ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳ ಅತ್ಯುತ್ತಮತೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ (ಪಿ § ಎನ್. ಪಿ. ಎಂದು ಊಹಿಸಿಕೊಳ್ಳಿ). ಉದಾಹರಣೆಗೆ, ಗ್ರಾಫ್ನಲ್ಲಿ ಗರಿಷ್ಠ ಕಡಿತವನ್ನು ಅಂದಾಜು ಮಾಡಲು ಗೋಯೆಮನ್ಸ್ ಮತ್ತು ವಿಲಿಯಮ್ಸನ್ ಅವರ ಅಲ್ಗಾರಿದಮ್ ಸಾಧಿಸಿದ ಅಂದಾಜು ಅನುಪಾತವು ಯಾವುದೇ ಸಂಯೋಜಕ ಸ್ಥಿರಾಂಕದೊಳಗೆ ಅನನ್ಯ ಆಟಗಳ ಊಹೆ ಮತ್ತು ಪಿ ≤ ಎನ್. ಪಿ. ಗೆ ಸೂಕ್ತವಾಗಿದೆ. ವಿಶಿಷ್ಟವಾದ ಆಟದ ಊಹೆಯು ಸೂಚಿಸುವ ಫಲಿತಾಂಶಗಳ ಪಟ್ಟಿಯನ್ನು ಪಕ್ಕದ ಕೋಷ್ಟಕದಲ್ಲಿ ದುರ್ಬಲ ಊಹೆಯಾದ ಪಿ ≤ ಎನ್. ಪಿ. ಗೆ ಅನುಗುಣವಾದ ಉತ್ತಮ ಫಲಿತಾಂಶಗಳೊಂದಿಗೆ ತೋರಿಸಲಾಗಿದೆ. ಒಂದು ಸ್ಥಿರಾಂಕ ಅಥವಾ ಎಂದರೆ ಪ್ರತಿ ಸ್ಥಿರಾಂಕಕ್ಕೂ (ಸಮಸ್ಯೆಯ ಗಾತ್ರಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ) ಫಲಿತಾಂಶವು ಅನುಕ್ರಮವಾಗಿ ಅದಕ್ಕಿಂತ ಹೆಚ್ಚು ಅಥವಾ ಕಡಿಮೆ ಇರುತ್ತದೆ. ಚರ್ಚೆ ಮತ್ತು ಪರ್ಯಾಯಗಳು ಪ್ರಸ್ತುತ, ವಿಶಿಷ್ಟ ಆಟದ ಊಹೆಯ ಸತ್ಯದ ಬಗ್ಗೆ ಯಾವುದೇ ಒಮ್ಮತವಿಲ್ಲ. ಊಹೆಯ ಕೆಲವು ಬಲವಾದ ರೂಪಗಳನ್ನು ನಿರಾಕರಿಸಲಾಗಿದೆ. ಬಹುಪದ-ಸಮಯದ ಕ್ರಮಾವಳಿಗಳಿಗೆ (ಆದರೆ ಬಹುಶಃ ಎನ್. ಪಿ.-ಹಾರ್ಡ್ ಅಲ್ಲ) ಒಂದು ವಿಶಿಷ್ಟ ಆಟದ ಮೌಲ್ಯವು ಕನಿಷ್ಠ ಮೌಲ್ಯವಿರುವ ಸಂದರ್ಭದಲ್ಲಿ ಪ್ರಕರಣವನ್ನು ಪ್ರತ್ಯೇಕಿಸುವುದು ಅಸಾಧ್ಯ ಎಂದು ಊಹೆಯ ವಿಭಿನ್ನ ರೂಪವು ಪ್ರತಿಪಾದಿಸುತ್ತದೆ. ಅಂದಾಜಿನ ಗಡಸುತನದ ಅನ್ವಯಗಳಿಗೆ ಊಹೆಯ ಈ ರೂಪವು ಇನ್ನೂ ಉಪಯುಕ್ತವಾಗಿದೆ. P = NP ಹೊರತು ಊಹೆಯ ಮೇಲಿನ ಸೂತ್ರೀಕರಣಗಳಲ್ಲಿನ ಸ್ಥಿರಾಂಕವು ಅಗತ್ಯವಾಗಿರುತ್ತದೆ. ಅನನ್ಯತೆಯ ಅಗತ್ಯವನ್ನು ತೆಗೆದುಹಾಕಿದರೆ, ಸಮಾನಾಂತರ ಪುನರಾವರ್ತನೆಯ ಪ್ರಮೇಯದಿಂದ ಅನುಗುಣವಾದ ಹೇಳಿಕೆಯು ನಿಜವೆಂದು ತಿಳಿದುಬಂದಿದೆ, ಮಾರೆಕ್ ಕಾರ್ಪಿನ್ಸ್ಕಿ ಮತ್ತು ವಾರೆನ್ ಶುಡಿ ಸಹ ವಿಶಿಷ್ಟ ಆಟದ ಸಮಸ್ಯೆಯ ದಟ್ಟವಾದ ನಿದರ್ಶನಗಳಿಗೆ ರೇಖೀಯ ಸಮಯದ ಅಂದಾಜು ಯೋಜನೆಗಳನ್ನು ನಿರ್ಮಿಸಿದ್ದಾರೆ. 2008 ರಲ್ಲಿ, ಪ್ರಸಾದ್ ರಾಘವೇಂದ್ರ ಅವರು ವಿಶಿಷ್ಟ ಆಟದ ಊಹೆಯು ನಿಜವಾಗಿದ್ದರೆ, ಪ್ರತಿ ನಿರ್ಬಂಧದ ತೃಪ್ತಿ ಸಮಸ್ಯೆಗೆ ಉತ್ತಮ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ನಿರ್ದಿಷ್ಟ ಸರಳ ಅರೆ-ಸೀಮಿತ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ನಿದರ್ಶನದಿಂದ ನೀಡಲಾಗುತ್ತದೆ, ಇದು ನಿರ್ದಿಷ್ಟವಾಗಿ ಬಹುಪದವಾಗಿದೆ. 2010ರಲ್ಲಿ, ಪ್ರಸಾದ್ ರಾಘವೇಂದ್ರ ಮತ್ತು ಡೇವಿಡ್ ಸ್ಟಿಯೂರರ್ ಅವರು ಗ್ಯಾಪ್-ಸ್ಮಾಲ್-ಸೆಟ್ ವಿಸ್ತರಣೆಯ ಸಮಸ್ಯೆಯನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಿದರು ಮತ್ತು ಇದು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಎಂದು ಊಹಿಸಿದರು. ಈ ಊಹೆಯು ವಿಶಿಷ್ಟ ಆಟದ ಊಹೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ಉಪಗ್ರಫ್ಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಅಂದಾಜು ಫಲಿತಾಂಶಗಳ ಬಲವಾದ ಗಡಸುತನವನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಸಹ ಇದನ್ನು ಬಳಸಲಾಗಿದೆ. 2010ರಲ್ಲಿ, ಸಂಜೀವ್ ಅರೋರಾ, ಬೋಆಜ್ ಬರಾಕ್ ಮತ್ತು ಡೇವಿಡ್ ಸ್ಟಿಯೂರರ್ ಅವರು ವಿಶಿಷ್ಟವಾದ ಆಟದ ಸಮಸ್ಯೆಗಾಗಿ ಸಬ್ಎಕ್ಸ್ಪೊನೆನ್ಷಿಯಲ್ ಟೈಮ್ ಅಪ್ರಾಕ್ಸಿಮೇಷನ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕಂಡುಹಿಡಿದರು. 2012ರಲ್ಲಿ, ಕನಿಷ್ಠ ಮೌಲ್ಯದ ನಿದರ್ಶನಗಳಿಂದ ಹೆಚ್ಚಿನ ಮೌಲ್ಯದ ನಿದರ್ಶನಗಳನ್ನು ಪ್ರತ್ಯೇಕಿಸುವುದು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಎಂದು ತೋರಿಸಲಾಗಿದೆ. 2018 ರಲ್ಲಿ, ಪ್ರಬಂಧಗಳ ಸರಣಿಯ ನಂತರ, 2-2 ಆಟಗಳ ಊಹೆಯೆಂದು ಕರೆಯಲ್ಪಡುವ ಊಹೆಯ ದುರ್ಬಲ ಆವೃತ್ತಿಯು ಸಾಬೀತಾಯಿತು. ಒಂದು ನಿರ್ದಿಷ್ಟ ಅರ್ಥದಲ್ಲಿ, ಇದು ಮೂಲ ಊಹೆಯ "ಅರ್ಧ" ವನ್ನು ಸಾಬೀತುಪಡಿಸುತ್ತದೆ. ಇದು ವಿಶಿಷ್ಟ ಲೇಬಲ್ ಕವರ್ಗೆ ತಿಳಿದಿರುವ ಅಂತರವನ್ನು ಸಹ ಸುಧಾರಿಸುತ್ತದೆಃ ಕನಿಷ್ಠ ಮೌಲ್ಯದ ನಿದರ್ಶನಗಳಿಂದ ಹೆಚ್ಚಿನ ಮೌಲ್ಯದ ನಿದರ್ಶನಗಳನ್ನು ಪ್ರತ್ಯೇಕಿಸುವುದು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿದೆ. ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳು. 2002 ಕಂಪ್ಯೂಟಿಂಗ್ನಲ್ಲಿ ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳು ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತ ಕಂಪ್ಯೂಟೇಶನಲ್ ಗಡಸುತನದ ಊಹೆಗಳು ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ ಪರಿಹರಿಸಲಾಗದ ಸಮಸ್ಯೆಗಳು ಊಹೆಗಳು