Random self-reducibility
ಯಾದೃಚ್ಛಿಕ ಸ್ವಯಂ-ಕಡಿಮೆಗೊಳಿಸುವಿಕೆ (ಆರ್ಎಸ್ಆರ್) ಎಂದರೆ ಸರಾಸರಿ ಪ್ರಕರಣಕ್ಕೆ ಉತ್ತಮ ಅಲ್ಗಾರಿದಮ್ ಕೆಟ್ಟ ಪ್ರಕರಣಕ್ಕೆ ಉತ್ತಮ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಆರ್ಎಸ್ಆರ್ ಎಂದರೆ ಒಂದು ಸಮಸ್ಯೆಯ ಎಲ್ಲಾ ನಿದರ್ಶನಗಳನ್ನು ದೊಡ್ಡ ಪ್ರಮಾಣದ ನಿದರ್ಶನಗಳನ್ನು ಪರಿಹರಿಸುವ ಸಾಮರ್ಥ್ಯ. ವ್ಯಾಖ್ಯಾನ ಯಾವುದೇ ನಿದರ್ಶನ x ಅನ್ನು ಮೌಲ್ಯಮಾಪನ ಮಾಡುವ f ಕಾರ್ಯಕ್ಕೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಒಂದು ಅಥವಾ ಹೆಚ್ಚಿನ ಯಾದೃಚ್ಛಿಕ ನಿದರ್ಶನಗಳಲ್ಲಿ yi ಮೇಲೆ f ಮೌಲ್ಯಮಾಪನಕ್ಕೆ ಕಡಿಮೆ ಮಾಡಬಹುದಾದರೆ, ಅದು ಸ್ವಯಂ-ಕಡಿತಗೊಳ್ಳುತ್ತದೆ (ಇದನ್ನು ಹೊಂದಾಣಿಕೆಯಲ್ಲದ ಏಕರೂಪದ ಸ್ವಯಂ-ಕಡಿತ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ). ಯಾದೃಚ್ಛಿಕ ಸ್ವಯಂ-ಕಡಿತದಲ್ಲಿ, f ಡೊಮೇನ್ನಲ್ಲಿರುವ ಅನಿಯಂತ್ರಿತ ಕೆಟ್ಟ-ನಿದರ್ಶನ x ಅನ್ನು ಯಾದೃಚ್ಛಿಕ ನಿದರ್ಶನಗಳ y1,., yk ಗೆ ಮ್ಯಾಪ್ ಮಾಡಲಾಗುತ್ತದೆ. ಮ್ಯಾಪಿಂಗ್, x, ಮತ್ತು f (y1),., f (yk) ನಿಂದ ನಾಣ್ಯ-ಟಾಸ್ ಅನುಕ್ರಮವನ್ನು ನೀಡಿದರೆ, ಬಹುಪದ ಸಮಯದಲ್ಲಿ f (x) ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಇದನ್ನು ಮಾಡಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ, yi ಮೇಲಿನ ಪ್ರೇರಿತ ವಿತರಣೆಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಸರಾಸರಿಯನ್ನು ತೆಗೆದುಕೊಳ್ಳುವಾಗ, f ನ ಸರಾಸರಿ-ಪ್ರಕರಣ ಸಂಕೀರ್ಣತೆಯು (ಬಹುಪದೀಯ ಅಂಶಗಳೊಳಗೆ) f ನ ಕೆಟ್ಟ-ಪ್ರಕರಣ ಯಾದೃಚ್ಛಿಕ ಸಂಕೀರ್ಣತೆಯಂತೆಯೇ ಇರುತ್ತದೆ. ಒಂದು ವಿಶೇಷ ನಿದರ್ಶನವೆಂದರೆ ಪ್ರತಿ ಯಾದೃಚ್ಛಿಕ ನಿದರ್ಶನ yi ಅನ್ನು |x | ಉದ್ದವನ್ನು ಹೊಂದಿರುವ f ಡೊಮೇನ್ನಲ್ಲಿರುವ ಅಂಶಗಳ ಸಂಪೂರ್ಣ ಗುಂಪಿನ ಮೇಲೆ ಏಕರೂಪವಾಗಿ ವಿತರಿಸಲಾಗುತ್ತದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ ಎಫ್ ಸರಾಸರಿ ಕೆಟ್ಟ ಸ್ಥಿತಿಯಷ್ಟೇ ಕಠಿಣವಾಗಿರುತ್ತದೆ. ಈ ವಿಧಾನವು ಎರಡು ಪ್ರಮುಖ ನಿರ್ಬಂಧಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಮೊದಲು y1,., ykಯ ಪೀಳಿಗೆಯನ್ನು ಹೊಂದಾಣಿಕೆಯಾಗದ ರೀತಿಯಲ್ಲಿ ನಡೆಸಲಾಗುತ್ತದೆ. ಇದರರ್ಥ f (y1) ಅನ್ನು ತಿಳಿಯುವ ಮೊದಲೇ y2 ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ. ಎರಡನೆಯದಾಗಿ, y1,., yk ಬಿಂದುಗಳನ್ನು ಏಕರೂಪವಾಗಿ ವಿತರಿಸುವ ಅಗತ್ಯವಿಲ್ಲ. ಕ್ರಿಪ್ಟೋಗ್ರಾಫಿಕ್ ಪ್ರೋಟೋಕಾಲ್ಗಳಲ್ಲಿನ ಅಪ್ಲಿಕೇಶನ್ ಡೇಟಾದಲ್ಲಿ ಸ್ವಲ್ಪ ಗೌಪ್ಯತೆಯ ಅಗತ್ಯವಿರುವ ಸಮಸ್ಯೆಗಳು (ಸಾಮಾನ್ಯವಾಗಿ ಕ್ರಿಪ್ಟೋಗ್ರಾಫಿಕ್ ಸಮಸ್ಯೆಗಳು) ಆ ಗೌಪ್ಯತೆಯನ್ನು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ಯಾದೃಚ್ಛಿಕತೆಯನ್ನು ಬಳಸಬಹುದು. ವಾಸ್ತವವಾಗಿ, ಸಾಬೀತುಪಡಿಸಬಹುದಾದ ಏಕೈಕ ಸುರಕ್ಷಿತ ಕ್ರಿಪ್ಟೋಗ್ರಾಫಿಕ್ ವ್ಯವಸ್ಥೆಯು (ಒನ್-ಟೈಮ್ ಪ್ಯಾಡ್) ಅದರ ಭದ್ರತೆಯನ್ನು ಹೊಂದಿದ್ದು, ವ್ಯವಸ್ಥೆಗೆ ಸರಬರಾಜು ಮಾಡಲಾದ ಪ್ರಮುಖ ದತ್ತಾಂಶದ ಯಾದೃಚ್ಛಿಕತೆಯ ಮೇಲೆ ಸಂಪೂರ್ಣವಾಗಿ ಅವಲಂಬಿತವಾಗಿದೆ. ಗೂಢಲಿಪೀಕರಣದ ಕ್ಷೇತ್ರವು ಕೆಲವು ಸಂಖ್ಯಾ-ಸೈದ್ಧಾಂತಿಕ ಕಾರ್ಯಗಳು ಯಾದೃಚ್ಛಿಕವಾಗಿ ಸ್ವಯಂ-ಕಡಿತಗೊಳಿಸಬಲ್ಲವು ಎಂಬ ಅಂಶವನ್ನು ಬಳಸಿಕೊಳ್ಳುತ್ತದೆ. ಇದು ಸಂಭವನೀಯ ಗೂಢಲಿಪೀಕರಣ ಮತ್ತು ಗೂಢಲಿಪೀಕರಣದ ದೃಷ್ಟಿಯಿಂದ ಬಲವಾದ ಸೂಡೊರಾಂಡಮ್ ಸಂಖ್ಯೆಯ ಉತ್ಪಾದನೆಯನ್ನು ಒಳಗೊಂಡಿದೆ. ಅಲ್ಲದೆ, ಉದಾಹರಣೆ-ಮರೆಮಾಚುವ ಯೋಜನೆಗಳು (ಅಲ್ಲಿ ದುರ್ಬಲ ಖಾಸಗಿ ಸಾಧನವು ತನ್ನ ದತ್ತಾಂಶವನ್ನು ಬಹಿರಂಗಪಡಿಸದೆ ಬಲವಾದ ಸಾರ್ವಜನಿಕ ಸಾಧನವನ್ನು ಬಳಸುತ್ತದೆ) ಯಾದೃಚ್ಛಿಕ ಸ್ವಯಂ-ಕಡಿತಗಳಿಂದ ಸುಲಭವಾಗಿ ಉದಾಹರಣೆಯಾಗಿವೆ. ಉದಾಹರಣೆಗಳುಃ ಪ್ರತ್ಯೇಕ ಲಾಗರಿಥಮ್ ಸಮಸ್ಯೆ, ಕ್ವಾಡ್ರಾಟಿಕ್ ರೆಸಿಡುಯಾಸಿಟಿ ಸಮಸ್ಯೆ, ಆರ್ಎಸ್ಎ ಇನ್ವರ್ಷನ್ ಸಮಸ್ಯೆ ಮತ್ತು ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಪರ್ಮನೆಂಟ್ ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಸಮಸ್ಯೆ ಇವೆಲ್ಲವೂ ಯಾದೃಚ್ಛಿಕ ಸ್ವಯಂ-ಕಡಿಮೆ ಮಾಡಬಹುದಾದ ಸಮಸ್ಯೆಗಳಾಗಿವೆ. ಪ್ರತ್ಯೇಕ ಲಾಗರಿಥಮ್ ಪ್ರಮೇಯ-|G | ಗಾತ್ರದ ಒಂದು ಆವರ್ತಕ ಗುಂಪು G ಅನ್ನು ನೀಡಲಾಗಿದೆ. ಒಂದು ನಿರ್ಣಾಯಕ ಬಹುಪದ ಸಮಯದ ಕ್ರಮಾವಳಿ Aಯು ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳ 1/ಪಾಲಿ (n) ಭಾಗಕ್ಕೆ ಪ್ರತ್ಯೇಕ ಲಾಗರಿಥಮ್ ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿದರೆ (ಇಲ್ಲಿ n = ಲಾಗ್ |G | ಇನ್ಪುಟ್ ಗಾತ್ರವಾಗಿದೆ), ನಂತರ ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳಿಗೆ ಪ್ರತ್ಯೇಕ ಲಾಗರಿಥಮ್ಗಾಗಿ ಯಾದೃಚ್ಛಿಕ ಬಹುಪದ ಸಮಯ ಕ್ರಮಾವಳಿ ಇರುತ್ತದೆ. G = {gi | 0 ≤ i <|G |} ಎಂಬ ಆವರ್ತಕ ಗುಂಪಿನ ಒಂದು ಜನರೇಟರ್ g ಮತ್ತು x ω G ಅನ್ನು ನೀಡಿದರೆ, ಮೂಲ g ಗೆ x ನ ಪ್ರತ್ಯೇಕ ಲಾಗ್ x = gk ನೊಂದಿಗೆ ಪೂರ್ಣಾಂಕ k (0 ≤ k <|G |) ಆಗಿದೆ. ಬಿ ಅನ್ನು {0,., |G | −1} ನಲ್ಲಿ ಏಕರೂಪವಾಗಿ ವಿತರಿಸಲು ತೆಗೆದುಕೊಳ್ಳಿ, ನಂತರ xgB = gk + B ಅನ್ನು ಸಹ G ಯಲ್ಲಿ ಏಕರೂಪವಾಗಿ ವಿತರಿಸಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ xgB ಯು x ನಿಂದ ಸ್ವತಂತ್ರವಾಗಿದೆ, ಮತ್ತು ಅದರ ಲಾಗರಿಥಮ್ ಅನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಸಂಭವನೀಯತೆ 1/ಪಾಲಿ (n) ನೊಂದಿಗೆ ಲೆಕ್ಕ ಹಾಕಬಹುದು. ನಂತರ loggx ಷ್ಣ loggxgB-B (ಮಾಡ್ |G |) ಮತ್ತು ಪ್ರತ್ಯೇಕ ಲಾಗರಿದಮ್ ಅನ್ನು ಸ್ವಯಂ-ಕಡಿತಗೊಳಿಸಬಹುದು. ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಪರ್ಮನೆಂಟ್ ವ್ಯಾಖ್ಯಾನವನ್ನು ನೀಡಿದರೆ, ಯಾವುದೇ n-ಬೈ-n ಮ್ಯಾಟ್ರಿಕ್ಸ್ M ಗೆ PERM (M) ಎಂಬುದು M ನಲ್ಲಿನ ನಮೂದುಗಳ ಮೇಲೆ ಡಿಗ್ರಿ n ನ ಬಹುವಿಧದ ಬಹುಪದವಾಗಿದೆ ಎಂಬುದು ಸ್ಪಷ್ಟವಾಗುತ್ತದೆ. ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಪರ್ಮನೆಂಟ್ ಅನ್ನು ಲೆಕ್ಕ ಹಾಕುವುದು ಕಷ್ಟಕರವಾದ ಕಂಪ್ಯೂಟೇಶನಲ್ ಕಾರ್ಯವಾಗಿದೆ-PERM ಅನ್ನು #P-ಕಂಪ್ಲೀಟ್ (ಪ್ರೂಫ್) ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ಇದಲ್ಲದೆ, ಹೆಚ್ಚಿನ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳಿಗೆ PERM (M) ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಸಾಮರ್ಥ್ಯವು ಎಲ್ಲಾ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳಿಗೆ PERM (M) ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಯಾದೃಚ್ಛಿಕ ಪ್ರೋಗ್ರಾಂನ ಅಸ್ತಿತ್ವವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಇದು PERM ಯಾದೃಚ್ಛಿಕವಾಗಿ ಸ್ವಯಂ-ಕಡಿತಗೊಳಿಸಬಲ್ಲದು ಎಂಬುದನ್ನು ತೋರಿಸುತ್ತದೆ. ಕೆಳಗಿನ ಚರ್ಚೆಯು ಕೆಲವು ಅವಿಭಾಜ್ಯ p ಗೆ ಸೀಮಿತ ಕ್ಷೇತ್ರ Fp ಯಿಂದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ನಮೂದುಗಳನ್ನು ಎಳೆಯುವ ಪ್ರಕರಣವನ್ನು ಪರಿಗಣಿಸುತ್ತದೆ ಮತ್ತು ಅಲ್ಲಿ ಎಲ್ಲಾ ಅಂಕಗಣಿತವನ್ನು ಆ ಕ್ಷೇತ್ರದಲ್ಲಿ ನಡೆಸಲಾಗುತ್ತದೆ. X ಎಂಬುದು Fp ಯಿಂದ ನಮೂದುಗಳನ್ನು ಹೊಂದಿರುವ ಯಾದೃಚ್ಛಿಕ n-ಬೈ-n ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿರಲಿ. ಯಾವುದೇ ಮ್ಯಾಟ್ರಿಕ್ಸ್ M + kX ನ ಎಲ್ಲಾ ನಮೂದುಗಳು k ನ ರೇಖೀಯ ಕಾರ್ಯಗಳಾಗಿರುವುದರಿಂದ, PERM (M) ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಡಿಗ್ರಿ n ಮಲ್ಟಿವೇರಿಯೇಟ್ ಬಹುಪದದೊಂದಿಗೆ ಆ ರೇಖೀಯ ಕಾರ್ಯಗಳನ್ನು ರಚಿಸುವ ಮೂಲಕ ನಾವು k ಮೇಲೆ ಮತ್ತೊಂದು ಡಿಗ್ರಿ n ಬಹುಪದವನ್ನು ಪಡೆಯುತ್ತೇವೆ, ಅದನ್ನು ನಾವು p (k) ಎಂದು ಕರೆಯುತ್ತೇವೆ. ಸ್ಪಷ್ಟವಾಗಿ, p (0) ಎಂಬುದು M ನ ಶಾಶ್ವತಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ಹೆಚ್ಚಿನ n-by-n ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳಿಗೆ PERM (A) ನ ಸರಿಯಾದ ಮೌಲ್ಯವನ್ನು Fp---- ನಿರ್ದಿಷ್ಟವಾಗಿ, 1−1/(3n) ನಿಂದ ನಮೂದುಗಳೊಂದಿಗೆ ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಪ್ರೋಗ್ರಾಂ ನಮಗೆ ತಿಳಿದಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ನಂತರ ಸರಿಸುಮಾರು ಮೂರನೇ ಎರಡರಷ್ಟು ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ, ನಾವು k = 1,2,., n + 1 ಗಾಗಿ PERM (M + kX) ಅನ್ನು ಲೆಕ್ಕ ಹಾಕಬಹುದು. ಒಮ್ಮೆ ನಾವು ಆ n + 1 ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ನಾವು p (k) ನ ಗುಣಾಂಕಗಳಿಗೆ ಅಂತರ್ವೇಶನವನ್ನು ಬಳಸಿ ಪರಿಹರಿಸಬಹುದು (p (k) ಡಿಗ್ರಿ n ಅನ್ನು ಹೊಂದಿದೆ ಎಂಬುದನ್ನು ನೆನಪಿನಲ್ಲಿಡಿ). ಒಮ್ಮೆ ನಾವು p (k) ಅನ್ನು ನಿಖರವಾಗಿ ತಿಳಿದುಕೊಂಡರೆ, ನಾವು p (0) ಅನ್ನು ಮೌಲ್ಯಮಾಪನ ಮಾಡುತ್ತೇವೆ, ಇದು PERM (M) ಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ. ನಾವು ಹಾಗೆ ಮಾಡಿದರೆ, ನಾವು 1/3 ಬಾರಿ ತಪ್ಪಾಗುವ ಅಪಾಯವನ್ನು ಎದುರಿಸುತ್ತೇವೆ, ಆದರೆ ಅನೇಕ ಯಾದೃಚ್ಛಿಕ X ಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಮೂಲಕ ಮತ್ತು ಮೇಲಿನ ಕಾರ್ಯವಿಧಾನವನ್ನು ಅನೇಕ ಬಾರಿ ಪುನರಾವರ್ತಿಸುವ ಮೂಲಕ, ಮತ್ತು ಬಹುಪಾಲು ವಿಜೇತರನ್ನು ಮಾತ್ರ ಉತ್ತರವಾಗಿ ಒದಗಿಸುವ ಮೂಲಕ, ನಾವು ದೋಷದ ಪ್ರಮಾಣವನ್ನು ಬಹಳ ಕಡಿಮೆ ಮಾಡಬಹುದು. ಪರಿಣಾಮಗಳು ಒಂದು ಎನ್. ಪಿ.-ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆಯು ಹೊಂದಾಣಿಕೆಯಿಲ್ಲದೆ ಯಾದೃಚ್ಛಿಕವಾಗಿ ಸ್ವಯಂ-ಕಡಿತಗೊಳಿಸಬಹುದಾದರೆ ಬಹುಪದೀಯ ಕ್ರಮಾನುಗತವು σ3 ಗೆ ಕುಸಿಯುತ್ತದೆ. ಒಂದು ಸಿ. ಓ. ಎನ್. ಪಿ-ಕಠಿಣ ಸಮಸ್ಯೆಯು ಒ (ಲಾಗ್ ಎನ್/ಎನ್) ನಲ್ಲಿ ಯಾದೃಚ್ಛಿಕವಾಗಿ ಸ್ವಯಂ-ಕಡಿತಗೊಳಿಸಬಹುದಾದರೆ, σ2 = Π2 ಆಗಿರುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಎಂ. ಅಬಾಡಿ, ಜೆ. ಫೈಗೆನ್ಬಾಮ್, ಮತ್ತು ಜೆ. ಕಿಲಿಯನ್, ಆನ್ ಹೈಡಿಂಗ್ ಇನ್ಫರ್ಮೇಷನ್ ಫ್ರಮ್ ಆನ್ ಒರಾಕಲ್, ಜೆ. ಕಂಪ್ಯೂಟ್. ಸಿಸ್ಟ್. ಸೈನ್ಸ್., 1989 ಎಸ್. ಅರೋರಾ, ಅರೌಂಡ್ ದಿ ಪಿಸಿಪಿ ಥೀರಂ, 1996 ಜೆ. ಫೈಗೆನ್ಬಾಮ್, ಎಲ್. ಫೋರ್ಟ್ನೋ, ಆನ್ ದಿ ರಾಂಡಮ್-ಸೆಲ್ಫ್-ರಿಡ್ಯುಸಿಬಿಲಿಟಿ ಆಫ್ ಕಂಪ್ಲೀಟ್ ಸೆಟ್ಸ್, 1991 ಯಾದೃಚ್ಛಿಕ ಕ್ರಮಾವಳಿಗಳು