R (complexity)
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಆರ್ ಎಂಬುದು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಪರಿಹರಿಸಬಹುದಾದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳ ವರ್ಗವಾಗಿದೆ, ಇದು ಎಲ್ಲಾ ಪುನರಾವರ್ತಿತ ಭಾಷೆಗಳ ಸಮೂಹವಾಗಿದೆ (ನಿರ್ಣಾಯಕ ಭಾಷೆಗಳು ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ). ಸಮಾನ ಸೂತ್ರೀಕರಣಗಳು ಆರ್ ಈ ಅರ್ಥದಲ್ಲಿ ಎಲ್ಲಾ ಒಟ್ಟು ಗಣನೀಯ ಕಾರ್ಯಗಳ ಗುಂಪಿಗೆ ಸಮನಾಗಿರುತ್ತದೆಃ ಒಂದು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯು ಆರ್ ನಲ್ಲಿದ್ದರೆ ಮತ್ತು ಅದರ ಸೂಚಕ ಕಾರ್ಯವು ಗಣನಾರ್ಹವಾಗಿದ್ದರೆ ಮಾತ್ರ, ಅದರ ಗ್ರಾಫ್ ಆರ್ ನಲ್ಲಿದ್ದರೆ ಮಾತ್ರ ಒಟ್ಟು ಕಾರ್ಯವನ್ನು ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ಇತರ ವರ್ಗಗಳೊಂದಿಗೆ ಸಂಬಂಧ ಗುರುತಿಸುವವರು ಮತ್ತು ಸಹ-ಗುರುತಿಸುವವರು ಇರುವ ಯಾವುದೇ ಸಮಸ್ಯೆಯನ್ನು ನಾವು ನಿರ್ಧರಿಸಬಹುದಾದ್ದರಿಂದ, ಒಬ್ಬರು ಫಲಿತಾಂಶವನ್ನು ಪಡೆಯುವವರೆಗೆ ಅವುಗಳನ್ನು ಸರಳವಾಗಿ ಇಂಟರ್ಲಿವ್ ಮಾಡುವ ಮೂಲಕ, ವರ್ಗವು ಆರ್ಇ ಸಹ-ಆರ್ಇಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ. ಬ್ಲಮ್, ಲೆನೋರ್, ಮೈಕ್ ಶುಬ್, ಮತ್ತು ಸ್ಟೀವ್ ಸ್ಮೇಲ್, (1989), "ಆನ್ ಎ ಥಿಯರಿ ಆಫ್ ಕಂಪ್ಯೂಟೇಶನ್ ಅಂಡ್ ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಓವರ್ ದಿ ರಿಯಲ್ ನಂಬರ್ಸ್ಃ ಎನ್. ಪಿ-ಕಂಪ್ಲೀಟೆನೆಸ್, ರಿಕರ್ಸಿವ್ ಫಂಕ್ಷನ್ಗಳು ಅಂಡ್ ಯೂನಿವರ್ಸಲ್ ಮೆಷೀನ್ಸ್", ಅಮೆರಿಕನ್ ಮ್ಯಾಥಮೆಟಿಕಲ್ ಸೊಸೈಟಿಯ ಬುಲೆಟಿನ್, ನ್ಯೂ ಸೀರೀಸ್, 21 (1): 1-46. ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಸಂಕೀರ್ಣತೆ ತರಗತಿಗಳು