PCP theorem
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಪಿಸಿಪಿ ಪ್ರಮೇಯವು (ಪಿಸಿಪಿ ಕ್ಯಾರೆಕ್ಟರೈಸೇಶನ್ ಪ್ರಮೇಯ ಎಂದೂ ಕರೆಯಲ್ಪಡುತ್ತದೆ) ಎನ್ಪಿ ಸಂಕೀರ್ಣತೆ ವರ್ಗದ ಪ್ರತಿಯೊಂದು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯು ಸ್ಥಿರವಾದ ಪ್ರಶ್ನೆಯ ಸಂಕೀರ್ಣತೆ ಮತ್ತು ಲಾಗರಿಥಮಿಕ್ ಯಾದೃಚ್ಛಿಕ ಸಂಕೀರ್ಣತೆಯ (ಯಾದೃಚ್ಛಿಕ ಬಿಟ್ಗಳ ಲಾಗರಿಥಮಿಕ್ ಸಂಖ್ಯೆಯನ್ನು ಬಳಸುತ್ತದೆ) ಸಂಭವನೀಯವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆಗಳನ್ನು (ಯಾದೃಚ್ಛಿಕ ಅಲ್ಗಾರಿದಮ್ನಿಂದ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆಗಳು) ಹೊಂದಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಕೆಲವು ಸಾರ್ವತ್ರಿಕ ಸ್ಥಿರಾಂಕವಾದ K ಗೆ, ಪ್ರತಿ n ಗೆ, n ಉದ್ದದ ಹೇಳಿಕೆಗೆ ಯಾವುದೇ ಗಣಿತದ ಪುರಾವೆಯನ್ನು ಉದ್ದದ ಪಾಲಿ (n) ನ ವಿಭಿನ್ನ ಪುರಾವೆಯಾಗಿ ಪುನಃ ಬರೆಯಬಹುದು ಎಂದು PCP ಪ್ರಮೇಯವು ಹೇಳುತ್ತದೆ, ಇದು ಯಾದೃಚ್ಛಿಕ ಅಲ್ಗಾರಿದಮ್ನಿಂದ 99 ಪ್ರತಿಶತ ನಿಖರತೆಯೊಂದಿಗೆ ಔಪಚಾರಿಕವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ ಆ ಪುರಾವೆಯ K ಅಕ್ಷರಗಳನ್ನು ಮಾತ್ರ ಪರಿಶೀಲಿಸುತ್ತದೆ. ವಿವಿಧ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳಿಗೆ ಸಮರ್ಥವಾದ ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸುವಲ್ಲಿ ಅಂತರ್ಗತವಾದ ಕಷ್ಟವನ್ನು ತನಿಖೆ ಮಾಡುವ ಅಂದಾಜುಗಳ ಕಂಪ್ಯೂಟೇಶನಲ್ ಗಡಸುತನದ ಸಿದ್ಧಾಂತಕ್ಕೆ ಪಿಸಿಪಿ ಪ್ರಮೇಯವು ಮೂಲಾಧಾರವಾಗಿದೆ. ಇದನ್ನು ಇಂಗೋ ವೆಜೆನರ್ ಅವರು "ಕುಕ್ ಅವರ ಪ್ರಮೇಯದ ನಂತರದ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದ ಅತ್ಯಂತ ಪ್ರಮುಖ ಫಲಿತಾಂಶ" ಮತ್ತು ಓಡೆಡ್ ಗೋಲ್ಡ್ರಿಚ್ ಅವರು "ನವೀನ ವಿಚಾರಗಳಿಂದ ಸಮೃದ್ಧವಾದ ಪ್ರಭಾವಶಾಲಿ ಕೃತಿಗಳ ಸರಣಿಯ ಪರಾಕಾಷ್ಠೆ" ಎಂದು ವಿವರಿಸಿದ್ದಾರೆ. ಔಪಚಾರಿಕ ಹೇಳಿಕೆ ಪಿಸಿಪಿ ಪ್ರಮೇಯವು ಎನ್ಪಿ = ಪಿಸಿಪಿ [ಒ (ಲಾಗ್ ಎನ್), ಒ (1)] ಎಂದು ಹೇಳುತ್ತದೆ, ಅಲ್ಲಿ ಪಿಸಿಪಿ [ಆರ್ (ಎನ್), ಕ್ಯೂ (ಎನ್)] ಎಂಬುದು ಪರಿಹಾರದ ಸಂಭವನೀಯವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆಯನ್ನು ನೀಡಬಹುದಾದ ಸಮಸ್ಯೆಗಳ ವರ್ಗವಾಗಿದೆ, ಅಂದರೆ ಯಾದೃಚ್ಛಿಕತೆಯ ಆರ್ (ಎನ್) ಬಿಟ್ಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಬಹುಪದಿಯಲ್ಲಿ ಪುರಾವೆಯನ್ನು ಪರಿಶೀಲಿಸಬಹುದು ಮತ್ತು ಪುರಾವೆಯ ಕ್ಯೂ (ಎನ್) ಬಿಟ್ಗಳನ್ನು ಓದುವ ಮೂಲಕ, ಸರಿಯಾದ ಪುರಾವೆಗಳನ್ನು ಯಾವಾಗಲೂ ಸ್ವೀಕರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ತಪ್ಪಾದ ಪುರಾವೆಗಳನ್ನು ಕನಿಷ್ಠ 1/2 ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ತಿರಸ್ಕರಿಸಲಾಗುತ್ತದೆ. n ಎಂಬುದು ಸಮಸ್ಯೆಯ ನಿದರ್ಶನದ ವಿವರಣೆಯ ಬಿಟ್ಗಳಲ್ಲಿನ ಉದ್ದವಾಗಿದೆ. ಪರಿಶೀಲನಾ ಕ್ರಮಾವಳಿಯು ಹೊಂದಾಣಿಕೆಯಾಗುವುದಿಲ್ಲ ಎಂಬುದನ್ನು ಮತ್ತಷ್ಟು ಗಮನಿಸಿಃ ಪರಿಶೀಲಿಸಲು ಪುರಾವೆಯ ತುಣುಕುಗಳ ಆಯ್ಕೆಯು ಯಾದೃಚ್ಛಿಕ ತುಣುಕುಗಳು ಮತ್ತು ಸಮಸ್ಯೆಯ ನಿದರ್ಶನದ ವಿವರಣೆಯನ್ನು ಮಾತ್ರ ಅವಲಂಬಿಸಿರುತ್ತದೆ, ಪುರಾವೆಯ ನಿಜವಾದ ತುಣುಕುಗಳಲ್ಲ. ಪಿಸಿಪಿ ಮತ್ತು ಅಂದಾಜು ಗಡಸುತನ ಪಿಸಿಪಿ ಪ್ರಮೇಯದ ಪರ್ಯಾಯ ಸೂತ್ರೀಕರಣವು ನಿರ್ಬಂಧದ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಯ ತೃಪ್ತಿಕರ ನಿರ್ಬಂಧಗಳ ಗರಿಷ್ಠ ಭಾಗವು ಕೆಲವು ಸ್ಥಿರ ಅಂಶದೊಳಗೆ ಅಂದಾಜು ಮಾಡಲು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಔಪಚಾರಿಕವಾಗಿ, ಕೆಲವು ಸ್ಥಿರಾಂಕಗಳಾದ q ಮತ್ತು α <1 ಗೆ, ಈ ಕೆಳಗಿನ ಭರವಸೆಯ ಸಮಸ್ಯೆಯು (ಲೈಸ್, Lno) ಒಂದು NP-ಕಠಿಣ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯಾಗಿದೆಃ ಲೈಸ್ = {φ: ಎಲ್ಲಾ ನಿರ್ಬಂಧಗಳು ಏಕಕಾಲದಲ್ಲಿ ತೃಪ್ತಿಕರವಾಗಿರುತ್ತವೆ} Lno = {φ: ಪ್ರತಿ ನಿಯೋಜನೆಯು φ ನಿರ್ಬಂಧಗಳ α ಭಾಗಕ್ಕಿಂತ ಕಡಿಮೆ ಭಾಗವನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ, ಅಲ್ಲಿ φ ಎಂಬುದು ಪ್ರತಿ ನಿರ್ಬಂಧಕ್ಕೆ ಗರಿಷ್ಠ q ಅಸ್ಥಿರಗಳೊಂದಿಗೆ ಬೂಲಿಯನ್ ವರ್ಣಮಾಲೆಯ ಮೇಲೆ ನಿರ್ಬಂಧದ ತೃಪ್ತಿ ಸಮಸ್ಯೆಯಾಗಿದೆ (CSP). ಮೇಲೆ ತಿಳಿಸಲಾದ ವರ್ಗ ಪಿಸಿಪಿಯೊಂದಿಗಿನ ಸಂಪರ್ಕವನ್ನು ಒಂದು ಪುರಾವೆಯಲ್ಲಿ ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಬಿಟ್ಗಳ q ಅನ್ನು ಪರಿಶೀಲಿಸುವುದನ್ನು ಪುರಾವೆಯ ಆ ಬಿಟ್ಗಳ ಮೇಲೆ q ಬೂಲಿಯನ್ ಅಸ್ಥಿರಗಳಲ್ಲಿನ ನಿರ್ಬಂಧವನ್ನು ಮೌಲ್ಯಮಾಪನ ಮಾಡುವಂತೆ ಕಾಣಬಹುದು. ಪರಿಶೀಲನಾ ಕ್ರಮಾವಳಿಯು ಯಾದೃಚ್ಛಿಕತೆಯ ಒ (ಲಾಗ್ ಎನ್) ಬಿಟ್ಗಳನ್ನು ಬಳಸುವುದರಿಂದ, ಇದನ್ನು ಮೇಲೆ ವಿವರಿಸಿದಂತೆ ಪಾಲಿ (ಎನ್) ನಿರ್ಬಂಧಗಳೊಂದಿಗೆ ಸಿಎಸ್ಪಿ ಎಂದು ಪ್ರತಿನಿಧಿಸಬಹುದು. ಪಿ. ಸಿ. ಪಿ. ಪ್ರಮೇಯದ ಇತರ ಗುಣಲಕ್ಷಣವು ನಂತರ ವಾಗ್ದಾನದ ಷರತ್ತನ್ನು α = 1/2 ರೊಂದಿಗೆ ಖಾತರಿಪಡಿಸುತ್ತದೆಃ ಎನ್. ಪಿ. ಸಮಸ್ಯೆಯ ಉತ್ತರ ಹೌದು ಎಂದಾದರೆ, ಪ್ರತಿ ನಿರ್ಬಂಧವು (ಯಾದೃಚ್ಛಿಕ ಬಿಟ್ಗಳಿಗೆ ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯಕ್ಕೆ ಅನುಗುಣವಾದ) ತೃಪ್ತಿಕರವಾದ ನಿಯೋಜನೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ (ಸ್ವೀಕಾರಾರ್ಹ ಪುರಾವೆ); ಇಲ್ಲದಿದ್ದರೆ, ಯಾವುದೇ ಪುರಾವೆಯನ್ನು ಕನಿಷ್ಠ 1/2 ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ತಿರಸ್ಕರಿಸಬೇಕು, ಅಂದರೆ ಯಾವುದೇ ನಿಯೋಜನೆಯು 1/2 ಕ್ಕಿಂತ ಕಡಿಮೆ ನಿರ್ಬಂಧಗಳನ್ನು ಪೂರೈಸಬೇಕು (ಅಂದರೆ ಅದನ್ನು 1/2 ಕ್ಕಿಂತ ಕಡಿಮೆ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಸ್ವೀಕರಿಸಲಾಗುತ್ತದೆ). ಆದ್ದರಿಂದ, ಪ್ರಾಮಿಸ್ ಪ್ರಾಬ್ಲೆಮ್ನ ಅಲ್ಗಾರಿದಮ್ ಆಧಾರವಾಗಿರುವ ಎನ್ಪಿ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ, ಮತ್ತು ಆದ್ದರಿಂದ ಪ್ರಾಮಿಸ್ ಪ್ರಾಬ್ಲೆಮ್ ಎನ್ಪಿ ಹಾರ್ಡ್ ಆಗಿರಬೇಕು. ಈ ಪ್ರಮೇಯದ ಪರಿಣಾಮವಾಗಿ, ಗರಿಷ್ಠ ಬೂಲಿಯನ್ ಸೂತ್ರದ ತೃಪ್ತಿ, ಗ್ರಾಫ್ಗಳಲ್ಲಿನ ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಸೆಟ್ ಮತ್ತು ಲ್ಯಾಟಿಸ್ಗಳ ಕಡಿಮೆ ವೆಕ್ಟರ್ ಸಮಸ್ಯೆಯನ್ನು ಒಳಗೊಂಡಂತೆ ಅನೇಕ ನೈಸರ್ಗಿಕ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳಿಗೆ ಪರಿಹಾರಗಳನ್ನು ಪಿ = ಎನ್ಪಿ ಹೊರತು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಅಂದಾಜು ಮಾಡಲಾಗುವುದಿಲ್ಲ ಎಂದು ತೋರಿಸಬಹುದು. ಮೇಲಿನ ರೂಪದ ಭರವಸೆಯ ಸಮಸ್ಯೆಗೆ ಅಂತಹ ಸಮಸ್ಯೆಗಳಿಗೆ ಪರಿಹಾರವನ್ನು ಅಂದಾಜು ಮಾಡುವ ಸಮಸ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುವ ಮೂಲಕ ಇದನ್ನು ಮಾಡಬಹುದು. ಈ ಫಲಿತಾಂಶಗಳನ್ನು ಕೆಲವೊಮ್ಮೆ ಪಿಸಿಪಿ ಪ್ರಮೇಯಗಳು ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ ಏಕೆಂದರೆ ಅವುಗಳನ್ನು ಕೆಲವು ಹೆಚ್ಚುವರಿ ರಚನೆಯೊಂದಿಗೆ ಎನ್ಪಿಗೆ ಸಂಭವನೀಯವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆಗಳಾಗಿ ನೋಡಬಹುದು. ದುರ್ಬಲ ಫಲಿತಾಂಶದ ಪುರಾವೆ, ಎನ್ಪಿ ಪಿಸಿಪಿ [ಎನ್3,1] ಅನ್ನು ಡೆಕ್ಸ್ಟರ್ ಕೋಝೆನ್ ಅವರ ಒಂದು ಉಪನ್ಯಾಸದಲ್ಲಿ ನೀಡಲಾಗಿದೆ. ಪಿ. ಸಿ. ಪಿ. ಪ್ರಮೇಯವು ಸಂವಾದಾತ್ಮಕ ಪುರಾವೆಗಳು ಮತ್ತು ಸಂಭವನೀಯವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆಗಳ ಮೇಲೆ ಸುದೀರ್ಘವಾದ ಕೆಲಸದ ಪರಾಕಾಷ್ಠೆಯಾಗಿದೆ. ಪ್ರಮಾಣಿತ ಪುರಾವೆಗಳು ಮತ್ತು ಸಂಭವನೀಯವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆಗಳಿಗೆ ಸಂಬಂಧಿಸಿದ ಮೊದಲ ಪ್ರಮೇಯವೆಂದರೆ NEXP [ಪಾಲಿ (ಎನ್), ಪಾಲಿ (ಎನ್)] ಎಂದು ಸಾಬೀತುಪಡಿಸಿದ ಹೇಳಿಕೆಯಾಗಿದೆ. ಮೊದಲಕ್ಷರಗಳ ಮೂಲವನ್ನು ಸಂಭಾವ್ಯವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆಯಲ್ಲಿ ಪಿಸಿಪಿಸಿ (ಎನ್), ಎಸ್ (ಎನ್) [ಆರ್ (ಎನ್), ಕ್ಯೂ (ಎನ್)] ಸಂಕೇತವನ್ನು ವಿವರಿಸಲಾಗಿದೆ. ಸಂಕೇತವು ಒಂದು ನಿರ್ದಿಷ್ಟ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗವನ್ನು ಹಿಂದಿರುಗಿಸುವ ಕಾರ್ಯವಾಗಿದೆ. ಮೇಲೆ ತಿಳಿಸಿದ ವಿವರಣೆಯನ್ನು ನೋಡಿ. ಈ ಪ್ರಮೇಯದ ಹೆಸರು ("ಪಿಸಿಪಿ ಪ್ರಮೇಯ") ಬಹುಶಃ "ಪಿಸಿಪಿ" ಎಂದರೆ "ಸಂಭವನೀಯವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ ಪುರಾವೆ" ಅಥವಾ ಮೇಲೆ ತಿಳಿಸಲಾದ ಸಂಕೇತದಿಂದ (ಅಥವಾ ಎರಡೂ) ಬರುತ್ತದೆ. [1990 ರಲ್ಲಿ] ತರುವಾಯ, ಈ ಕೃತಿಯಲ್ಲಿ ಬಳಸಿದ ವಿಧಾನಗಳನ್ನು 1991 ರಲ್ಲಿ ಬಾಬಾಯ್, ಲ್ಯಾನ್ಸ್ ಫೋರ್ಟ್ನೋ, ಲೆವಿನ್ ಮತ್ತು ಸ್ಜೆಗ್ಡಿ, ಫೀಜ್, ಗೋಲ್ಡ್ವಾಸರ್, ಲುಂಡ್, ಸಫ್ರಾ ಮತ್ತು ಸ್ಜೆಗ್ಡಿ (1991), ಮತ್ತು ಅರೋರಾ ಮತ್ತು ಸಫ್ರಾ 1992 ರಲ್ಲಿ ಅರೋರಾ, ಲುಂಡ್, ಮೋಟ್ವಾನಿ, ಸುಡಾನ್ ಮತ್ತು ಸ್ಜೆಗ್ಡಿ ಅವರು 1998 ರಲ್ಲಿ ಪಿಸಿಪಿ ಪ್ರಮೇಯದ ಪುರಾವೆಯನ್ನು ನೀಡಿದರು. 2001ರ ಗೊಡೆಲ್ ಪ್ರಶಸ್ತಿಯನ್ನು ಸಂಜೀವ್ ಅರೋರಾ, ಉರಿಯೆಲ್ ಫೀಜ್, ಶಾಫಿ ಗೋಲ್ಡ್ವಾಸರ್, ಕಾರ್ಸ್ಟನ್ ಲುಂಡ್, ಲಾಸ್ಲೋ ಲೊವಾಸ್ಜ್, ರಾಜೀವ್ ಮೋಟ್ವಾನಿ, ಶ್ಮುಯೆಲ್ ಸಫ್ರಾ, ಮಧು ಸುಡಾನ್ ಮತ್ತು ಮಾರಿಯೋ ಸ್ಜೆಗ್ಡಿ ಅವರಿಗೆ ಪಿಸಿಪಿ ಪ್ರಮೇಯ ಮತ್ತು ಅಂದಾಜು ಕಠಿಣತೆಯೊಂದಿಗಿನ ಅದರ ಸಂಪರ್ಕಕ್ಕಾಗಿ ನೀಡಲಾಯಿತು. 2005ರಲ್ಲಿ ಇರಿಟ್ ದಿನೂರ್ ಅವರು ಎಕ್ಸ್ಪ್ಯಾಂಡರ್ ಗ್ರಾಫ್ಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಪಿಸಿಪಿ ಪ್ರಮೇಯದ ಗಮನಾರ್ಹವಾಗಿ ಸರಳವಾದ ಪುರಾವೆಯನ್ನು ಕಂಡುಹಿಡಿದರು. ಇದಕ್ಕಾಗಿ ಅವರು 2019ರ ಗೊಡೆಲ್ ಪ್ರಶಸ್ತಿಯನ್ನು ಪಡೆದರು. 2012ರಲ್ಲಿ, ಥಾಮಸ್ ವಿಡಿಕ್ ಮತ್ತು ತ್ಸುಯೋಶಿ ಇಟೊ ಅವರು ಒಂದು ಫಲಿತಾಂಶವನ್ನು ಪ್ರಕಟಿಸಿದರು, ಅದು "ಮಲ್ಟಿಪ್ಲೇಯರ್ ಆಟದಲ್ಲಿ ಸಿಕ್ಕಿಹಾಕಿಕೊಳ್ಳುವ ಸಮರ್ಥಕರ ಸಾಮರ್ಥ್ಯದ ಮೇಲೆ ಬಲವಾದ ಮಿತಿಯನ್ನು" ತೋರಿಸಿತು. ಇದು ಪಿಸಿಪಿ ಪ್ರಮೇಯದ ಕ್ವಾಂಟಮ್ ಸಾದೃಶ್ಯವನ್ನು ಸಾಬೀತುಪಡಿಸುವ ಒಂದು ಹೆಜ್ಜೆಯಾಗಿರಬಹುದು, ಏಕೆಂದರೆ ಫಲಿತಾಂಶವನ್ನು ಮಾಧ್ಯಮಗಳಲ್ಲಿ ವರದಿ ಮಾಡಿದಾಗ, ಪ್ರೊಫೆಸರ್ ಡೋರಿಟ್ ಅಹರೊನೊವ್ ಇದನ್ನು "ಮಲ್ಟಿಪ್ರೋವರ್ ಸಂವಾದಾತ್ಮಕ ಪುರಾವೆಗಳ ಮೇಲಿನ ಹಿಂದಿನ ಪ್ರಬಂಧದ ಕ್ವಾಂಟಮ್ ಸಾದೃಶ್ಯ" ಎಂದು ಕರೆದರು, ಅದು "ಮೂಲತಃ ಪಿಸಿಪಿ ಪ್ರಮೇಯಕ್ಕೆ ಕಾರಣವಾಯಿತು". 2018 ರಲ್ಲಿ, ಥಾಮಸ್ ವಿಡಿಕ್ ಮತ್ತು ಆನಂದ್ ನಟರಾಜನ್ ಯಾದೃಚ್ಛಿಕ ಕಡಿತದ ಅಡಿಯಲ್ಲಿ ಕ್ವಾಂಟಮ್ ಪಿಸಿಪಿ ಪ್ರಮೇಯದ ಆಟದ ರೂಪಾಂತರವನ್ನು ಸಾಬೀತುಪಡಿಸಿದರು. ಇದು ಹೇಳುವಂತೆ ಕ್ಯೂ. ಎಂ. ಎ. ಷ್. ಎಮ್. ಐ. ಪಿ. * [ಲಾಗ್ (ಎನ್), 1,1/2], ಅಲ್ಲಿ ಎಂ. ಐ. ಪಿ. * [ಎಫ್ (ಎನ್), ಸಿ, ಎಸ್] ಎಂಬುದು ಎಫ್ (ಎನ್)-ಬಿಟ್ ಶಾಸ್ತ್ರೀಯ ಸಂವಹನಗಳೊಂದಿಗೆ ಬಹು-ಪುರಾವೆ ಕ್ವಾಂಟಮ್ ಸಂವಾದಾತ್ಮಕ ಪುರಾವೆಗಳ ವ್ಯವಸ್ಥೆಗಳ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗವಾಗಿದೆ, ಮತ್ತು ಸಂಪೂರ್ಣತೆ ಸಿ ಮತ್ತು ಧ್ವನಿ ಎಸ್ ಆಗಿದೆ. ಅವರು ಕ್ವಾಂಟಮ್ ಪಿಸಿಪಿ ಊಹೆಯ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆವೃತ್ತಿಯನ್ನು ಸಹ ತೋರಿಸಿದರು, ಅವುಗಳೆಂದರೆ ಸ್ಥಿರ ಭರವಸೆಯ ಅಂತರ ಸಿ-ಎಸ್ ಹೊಂದಿರುವ ಸ್ಥಳೀಯ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಸಮಸ್ಯೆಯು ಕ್ಯೂಎಂಎ-ಕಠಿಣವಾಗಿದೆ, ಇದು ಆಟದ ಕ್ವಾಂಟಮ್ ಪಿಸಿಪಿ ಪ್ರಮೇಯವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಎನ್ಎಲ್ಟಿಎಸ್ ಊಹೆಯು ಮೂಲಭೂತವಾಗಿ ಪರಿಹರಿಸಲಾಗದ ಅಡಚಣೆಯಾಗಿದೆ ಮತ್ತು ಪಿಸಿಪಿಯ ಕ್ವಾಂಟಮ್ ಅನಲಾಗ್ಗೆ ಪೂರ್ವಸೂಚಕವಾಗಿದೆ. ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳು. .. .. .. .. .. ಯಾದೃಚ್ಛಿಕ ಕ್ರಮಾವಳಿಗಳು ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಪ್ರಮೇಯಗಳು