RE (complexity)
ಗಣನೀಯತೆ ಸಿದ್ಧಾಂತ ಮತ್ತು ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಆರ್ಇ (ಪುನರಾವರ್ತಿತವಾಗಿ ಎಣಿಸಬಹುದಾದ) ಎಂಬುದು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳ ವರ್ಗವಾಗಿದ್ದು, ಇದಕ್ಕಾಗಿ 'ಹೌದು' ಉತ್ತರವನ್ನು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಸೀಮಿತ ಸಮಯದಲ್ಲಿ ಪರಿಶೀಲಿಸಬಹುದು. ಅನೌಪಚಾರಿಕವಾಗಿ, ಒಂದು ಸಮಸ್ಯೆಯ ನಿದರ್ಶನಕ್ಕೆ ಉತ್ತರ 'ಹೌದು' ಎಂದಾದರೆ, ಇದನ್ನು ನಿರ್ಧರಿಸಲು ಸೀಮಿತ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುವ ಕೆಲವು ಕಾರ್ಯವಿಧಾನಗಳಿವೆ, ಮತ್ತು ನಿಜವಾದ ಉತ್ತರ 'ಇಲ್ಲ' ಆಗಿದ್ದಾಗ ಈ ಕಾರ್ಯವಿಧಾನವು ಎಂದಿಗೂ 'ಹೌದು' ಎಂದು ತಪ್ಪಾಗಿ ವರದಿ ಮಾಡುವುದಿಲ್ಲ. ಆದಾಗ್ಯೂ, ನಿಜವಾದ ಉತ್ತರ 'ಇಲ್ಲ' ಎಂದು ಬಂದಾಗ, ಕಾರ್ಯವಿಧಾನವನ್ನು ನಿಲ್ಲಿಸುವ ಅಗತ್ಯವಿಲ್ಲ; ಇದು ಕೆಲವು 'ಇಲ್ಲ' ಪ್ರಕರಣಗಳಿಗೆ 'ಅನಂತ ಲೂಪ್' ಗೆ ಹೋಗಬಹುದು. ಅಂತಹ ಕಾರ್ಯವಿಧಾನವನ್ನು ಕೆಲವೊಮ್ಮೆ ಅರೆ-ಕ್ರಮಾವಳಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಇದನ್ನು ಕ್ರಮಾವಳಿಗಳಿಂದ ಪ್ರತ್ಯೇಕಿಸಲು, ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗೆ ಸಂಪೂರ್ಣ ಪರಿಹಾರ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಅಂತೆಯೇ, ಕೋ-ಆರ್ಇ ಎಂಬುದು ಆರ್ಇ ಭಾಷೆಯಲ್ಲಿ ಒಂದು ಭಾಷೆಯ ಪೂರಕವಾಗಿರುವ ಎಲ್ಲಾ ಭಾಷೆಗಳ ಸಮೂಹವಾಗಿದೆ. ಒಂದು ಅರ್ಥದಲ್ಲಿ, ಕೋ-ಆರ್ಇ ಸದಸ್ಯತ್ವವನ್ನು ಸೀಮಿತ ಅವಧಿಯಲ್ಲಿ ನಿರಾಕರಿಸಬಹುದಾದ ಭಾಷೆಗಳನ್ನು ಒಳಗೊಂಡಿದೆ, ಆದರೆ ಸದಸ್ಯತ್ವವನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಶಾಶ್ವತವಾಗಿ ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ಸಮಾನ ವ್ಯಾಖ್ಯಾನವು ಸಮಾನವಾಗಿ, ಆರ್ಇ ಎಂಬುದು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳ ವರ್ಗವಾಗಿದ್ದು, ಇದಕ್ಕಾಗಿ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರವು ಎಲ್ಲಾ 'ಹೌದು' ನಿದರ್ಶನಗಳನ್ನು ಒಂದೊಂದಾಗಿ ಪಟ್ಟಿ ಮಾಡಬಹುದು (ಇದು 'ಎಣಿಸಬಹುದಾದ' ಎಂದರೆ). ಆರ್ಇಯ ಪ್ರತಿಯೊಂದು ಸದಸ್ಯರೂ ಪುನರಾವರ್ತಿತವಾಗಿ ಎಣಿಸಬಹುದಾದ ಗುಂಪಾಗಿದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಡಯೋಫಂಟೈನ್ ಗುಂಪಾಗಿದೆ. ಇದನ್ನು ಸಮಾನವೆಂದು ತೋರಿಸಲು, ಎಲ್ಲಾ ಸ್ವೀಕೃತ ಇನ್ಪುಟ್ಗಳನ್ನು ಎಣಿಸುವ ಯಂತ್ರವಿದ್ದರೆ, ಸ್ಟ್ರಿಂಗ್ನಲ್ಲಿ ತೆಗೆದುಕೊಳ್ಳುವ ಮತ್ತೊಂದು ಯಂತ್ರವು ಚಲಿಸಬಹುದು ಮತ್ತು ಸ್ಟ್ರಿಂಗನ್ನು ಎಣಿಸಿದರೆ ಸ್ವೀಕರಿಸಬಹುದು ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ಒಂದು ಇನ್ಪುಟ್ ಒಂದು ಭಾಷೆಯಲ್ಲಿದ್ದಾಗ ಯಂತ್ರವು ಸ್ವೀಕರಿಸಿದರೆ, ಮತ್ತೊಂದು ಯಂತ್ರವು ಪ್ರತಿ ಇನ್ಪುಟ್ನ ಸಿಮ್ಯುಲೇಶನ್ಗಳನ್ನು ಪರಸ್ಪರ ಬಿಡಿಸುವ ಮೂಲಕ ಮತ್ತು ಸ್ವೀಕರಿಸಲಾದ ತಂತಿಗಳನ್ನು ಔಟ್ಪುಟ್ ಮಾಡುವ ಮೂಲಕ ಭಾಷೆಯಲ್ಲಿನ ಎಲ್ಲಾ ತಂತಿಗಳನ್ನು ಎಣಿಸಬಹುದು (ಕಾರ್ಯಗತಗೊಳಿಸುವ ಕ್ರಮವು ಅಂತಿಮವಾಗಿ ಪ್ರತಿ ಕಾರ್ಯಗತಗೊಳಿಸುವ ಹಂತಕ್ಕೂ ತಲುಪುತ್ತದೆ ಏಕೆಂದರೆ ಲೆಕ್ಕವಿಲ್ಲದಷ್ಟು ಸಂಖ್ಯೆಯ ಜೋಡಿ ಇನ್ಪುಟ್ಗಳು ಮತ್ತು ಹಂತಗಳಿವೆ). ಇತರ ವರ್ಗಗಳೊಂದಿಗಿನ ಸಂಬಂಧಗಳು ಪುನರಾವರ್ತಿತ ಭಾಷೆಗಳ (ಆರ್) ಸಮೂಹವು ಆರ್ಇ ಮತ್ತು ಕೋ-ಆರ್ಇ ಎರಡರ ಉಪವಿಭಾಗವಾಗಿದೆ. ವಾಸ್ತವವಾಗಿ, ಇದು ಆ ಎರಡು ವರ್ಗಗಳ ಛೇದನವಾಗಿದೆ, ಏಕೆಂದರೆ ಗುರುತಿಸುವವರು ಮತ್ತು ಸಹ-ಗುರುತಿಸುವವರು ಇರುವ ಯಾವುದೇ ಸಮಸ್ಯೆಯನ್ನು ಒಬ್ಬರು ಫಲಿತಾಂಶವನ್ನು ಪಡೆಯುವವರೆಗೆ ಅವುಗಳನ್ನು ಪರಸ್ಪರ ಸೇರಿಸುವ ಮೂಲಕ ನಾವು ನಿರ್ಧರಿಸಬಹುದು. ಆದ್ದರಿಂದಃ ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ಆರ್ಇ ಅಥವಾ ಕೋ-ಆರ್ಇ ಇಲ್ಲದ ಭಾಷೆಗಳ ಗುಂಪನ್ನು ಎನ್ಆರ್ಎನ್ಸಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಇವು ಸೀಮಿತ ಅವಧಿಯಲ್ಲಿ ಸದಸ್ಯತ್ವ ಅಥವಾ ಸದಸ್ಯತ್ವವಿಲ್ಲದಿರುವುದನ್ನು ಸಾಬೀತುಪಡಿಸಲಾಗದ ಮತ್ತು ಆರ್ಇ ಅಥವಾ ಕೋ-ಆರ್ಇ ಅಲ್ಲದ ಎಲ್ಲಾ ಇತರ ಭಾಷೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಭಾಷೆಗಳ ಸಮೂಹವಾಗಿದೆ. ಅದುಃ. ಈ ಸಮಸ್ಯೆಗಳು ನಿರ್ಣಯಿಸಲಾಗದವು ಮಾತ್ರವಲ್ಲ, ಅವು ಅಥವಾ ಅವುಗಳ ಪೂರಕಗಳನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಎಣಿಸಲಾಗುವುದಿಲ್ಲ. 2020ರ ಜನವರಿಯಲ್ಲಿ, ಆರ್ಇ ವರ್ಗವು ಎಮ್ಐಪಿ * ಗೆ ಸಮಾನವಾಗಿದೆ ಎಂಬುದಕ್ಕೆ ಪೂರ್ವ ಮುದ್ರಣವು ಪುರಾವೆಯನ್ನು ಘೋಷಿಸಿತು (ಶಾಸ್ತ್ರೀಯ ಪರಿಶೀಲನಾ ಯಂತ್ರವು ಸಿಕ್ಕಿಹಾಕಿಕೊಳ್ಳುವ ಅನೇಕ ಸರ್ವಶಕ್ತ ಕ್ವಾಂಟಮ್ ಪ್ರೊವರ್ಗಳೊಂದಿಗೆ ಸಂವಹನ ನಡೆಸುವ ವರ್ಗ); ಪರಿಷ್ಕೃತ, ಆದರೆ ಇನ್ನೂ ಸಂಪೂರ್ಣವಾಗಿ ಪರಿಶೀಲಿಸದ, ಪುರಾವೆಯನ್ನು 2021ರ ನವೆಂಬರ್ನಲ್ಲಿ ಕಮ್ಯುನಿಕೇಷನ್ಸ್ ಆಫ್ ದಿ ಎಸಿಎಂನಲ್ಲಿ ಪ್ರಕಟಿಸಲಾಯಿತು. ಕಾನ್ಸ್ ಎಂಬೆಡಿಂಗ್ ಸಮಸ್ಯೆ ಮತ್ತು ಸಿರೆಲ್ಸನ್ರ ಸಮಸ್ಯೆ ಸುಳ್ಳು ಎಂದು ಪುರಾವೆ ಸೂಚಿಸುತ್ತದೆ. ರೀ-ಕಂಪ್ಲೀಟ್ ರೀ-ಕಂಪ್ಲೀಟ್ ಎಂಬುದು ಆರ್ಇಗೆ ಸಂಪೂರ್ಣವಾದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳ ಗುಂಪಾಗಿದೆ. ಒಂದು ಅರ್ಥದಲ್ಲಿ, ಇವು "ಕಠಿಣ" ಪುನರಾವರ್ತಿತವಾಗಿ ಎಣಿಸಬಹುದಾದ ಸಮಸ್ಯೆಗಳಾಗಿವೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಬಳಸುವ ಕಡಿತಗಳ ಮೇಲೆ ಯಾವುದೇ ನಿರ್ಬಂಧವನ್ನು ಇರಿಸಲಾಗುವುದಿಲ್ಲ, ಆದರೆ ಅವು ಅನೇಕ-ಒಂದು ಕಡಿತಗಳಾಗಿರಬೇಕು. ರೀ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಗಳ ಉದಾಹರಣೆಗಳುಃ ಸಮಸ್ಯೆಯನ್ನು ನಿಲ್ಲಿಸುವುದುಃ ಸೀಮಿತ ಇನ್ಪುಟ್ ನೀಡಲಾದ ಪ್ರೋಗ್ರಾಂ ಚಾಲನೆಯಲ್ಲಿದೆಯೇ ಅಥವಾ ಶಾಶ್ವತವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆಯೇ. ರೈಸ್ನ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಪುನರಾವರ್ತಿತ ಕಾರ್ಯಗಳ ಗುಂಪಿನ ಯಾವುದೇ ಕ್ಷುಲ್ಲಕವಲ್ಲದ ಉಪವಿಭಾಗದಲ್ಲಿ ಸದಸ್ಯತ್ವವನ್ನು ನಿರ್ಧರಿಸುವುದು ಆರ್ಇ-ಹಾರ್ಡ್ ಆಗಿದೆ. ಸೆಟ್ ಅನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಎಣಿಸಬಹುದಾದಾಗ ಅದು ಪೂರ್ಣಗೊಳ್ಳುತ್ತದೆ. ಎಲ್ಲಾ ಸೃಜನಶೀಲ ಸೆಟ್ಗಳು ಮರು-ಪೂರ್ಣಗೊಂಡಿವೆ ಎಂದು ಸಾಬೀತಾಯಿತು. ಗುಂಪುಗಳು ಅಥವಾ ಅರೆಗುಂಪುಗಳಿಗೆ ಏಕರೂಪದ ಪದದ ಸಮಸ್ಯೆ. (ವಾಸ್ತವವಾಗಿ, ಕೆಲವು ಪ್ರತ್ಯೇಕ ಗುಂಪುಗಳಿಗೆ ಸಮಸ್ಯೆ ಎಂಬ ಪದವು RE-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ.) ಸಾಮಾನ್ಯ ಅನಿಯಂತ್ರಿತ ಔಪಚಾರಿಕ ವ್ಯಾಕರಣದಲ್ಲಿ ಸದಸ್ಯತ್ವವನ್ನು ನಿರ್ಧರಿಸುವುದು. (ಮತ್ತೆ, ಕೆಲವು ಪ್ರತ್ಯೇಕ ವ್ಯಾಕರಣಗಳು RE-ಕಂಪ್ಲೀಟ್ ಸದಸ್ಯತ್ವದ ಸಮಸ್ಯೆಗಳನ್ನು ಹೊಂದಿವೆ.) ಮೊದಲ-ಕ್ರಮಾಂಕದ ತರ್ಕಕ್ಕೆ ಮಾನ್ಯತೆಯ ಸಮಸ್ಯೆ. ಪೋಸ್ಟ್ ಕರೆಸ್ಪಾಂಡೆನ್ಸ್ ಸಮಸ್ಯೆಃ ಜೋಡಿ ತಂತಿಗಳ ಪಟ್ಟಿಯನ್ನು ನೀಡಿದರೆ, ಈ ಜೋಡಿಗಳಿಂದ ಆಯ್ಕೆ ಇದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸಿ (ಪುನರಾವರ್ತನೆಗಳನ್ನು ಅನುಮತಿಸುತ್ತದೆ) ಅಂದರೆ ಮೊದಲ ವಸ್ತುಗಳ (ಜೋಡಿಗಳ) ಸಂಯೋಜನೆಯು ಎರಡನೇ ವಸ್ತುಗಳ ಸಂಯೋಜನೆಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ. ಡಯೋಫಂಟೈನ್ ಸಮೀಕರಣವು ಯಾವುದೇ ಪೂರ್ಣಾಂಕ ಪರಿಹಾರಗಳನ್ನು ಹೊಂದಿದೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವುದು. ಕೋ-ಆರ್ಇ-ಕಂಪ್ಲೀಟ್ ಸಹ-ಆರ್ಇ-ಕಂಪ್ಲೀಟ್ ಎನ್ನುವುದು ಕೋ-ಆರ್ಇಗೆ ಸಂಪೂರ್ಣವಾದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳ ಗುಂಪಾಗಿದೆ. ಒಂದು ಅರ್ಥದಲ್ಲಿ, ಇವು ಪುನರಾವರ್ತಿತವಾಗಿ ಎಣಿಸಬಹುದಾದ ಅತ್ಯಂತ ಕಠಿಣ ಸಮಸ್ಯೆಗಳ ಪೂರಕಗಳಾಗಿವೆ. ಕೋ-ಆರ್ಇ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಗಳ ಉದಾಹರಣೆಗಳುಃ ವಾಂಗ್ ಟೈಲ್ಗಳಿಗೆ ಡೊಮಿನೊ ಸಮಸ್ಯೆ. ಮೊದಲ-ಕ್ರಮಾಂಕದ ತರ್ಕಕ್ಕೆ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆ. ನಾತ್-ಬೆಂಡಿಕ್ಸ್ ಕಂಪ್ಲೀಷನ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸಹ ನೋಡಿ ಪಾಲಿಮಾರ್ಫಿಕ್ ರಿಕರ್ಶನ್ ರಿಷ್ ಅಲ್ಗಾರಿದಮ್ ಸೆಮಿಡೆಸಿಡೆಬಿಲಿಟಿ ರೆಫರೆನ್ಸಸ್ ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಕ್ಲಾಸ್ಗಳು ಅನಿರ್ದಿಷ್ಟ ಸಮಸ್ಯೆಗಳ ಪಟ್ಟಿ