Fagin's theorem
ಫಾಗಿನ್ನ ಪ್ರಮೇಯವು ವಿವರಣಾತ್ಮಕ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದ ಅತ್ಯಂತ ಹಳೆಯ ಫಲಿತಾಂಶವಾಗಿದೆ, ಇದು ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದ ಒಂದು ಶಾಖೆಯಾಗಿದ್ದು, ಆ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಕ್ರಮಾವಳಿಗಳ ವರ್ತನೆಯ ಬದಲು ಅವುಗಳ ಸಮಸ್ಯೆಗಳ ತರ್ಕ-ಆಧಾರಿತ ವಿವರಣೆಗಳ ಪರಿಭಾಷೆಯಲ್ಲಿ ಸಂಕೀರ್ಣತೆ ವರ್ಗಗಳನ್ನು ನಿರೂಪಿಸುತ್ತದೆ. ಅಸ್ತಿತ್ವವಾದದ ಎರಡನೇ ಕ್ರಮಾಂಕದ ತರ್ಕದಲ್ಲಿ ವ್ಯಕ್ತಪಡಿಸಬಹುದಾದ ಎಲ್ಲಾ ಗುಣಲಕ್ಷಣಗಳ ಗುಂಪನ್ನು ನಿಖರವಾಗಿ ಸಂಕೀರ್ಣತೆ ವರ್ಗ ಎನ್. ಪಿ. ಎಂದು ಪ್ರಮೇಯವು ಹೇಳುತ್ತದೆ. ಇದನ್ನು ರೊನಾಲ್ಡ್ ಫಾಗಿನ್ ಅವರು 1973 ರಲ್ಲಿ ತಮ್ಮ ಡಾಕ್ಟರೇಟ್ ಪ್ರಬಂಧದಲ್ಲಿ ಸಾಬೀತುಪಡಿಸಿದರು ಮತ್ತು ಅವರ 1974 ರ ಪ್ರಬಂಧದಲ್ಲಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತಾರೆ. ಎರಡನೇ ಕ್ರಮಾಂಕದ ಸೂತ್ರಕ್ಕೆ ಅಗತ್ಯವಾದ ಅರ್ಹತೆಯನ್ನು (ಒಂದು ದಿಕ್ಕಿನಲ್ಲಿ) ಸುಧಾರಿಸಲಾಗಿದೆ, ಮತ್ತು ಗ್ರ್ಯಾಂಡ್ಜೀನ್ನ ಹಲವಾರು ಫಲಿತಾಂಶಗಳು ಅನಿರ್ದಿಷ್ಟ ಯಾದೃಚ್ಛಿಕ-ಪ್ರವೇಶ ಯಂತ್ರಗಳ ಮೇಲೆ ಕಠಿಣವಾದ ಮಿತಿಯನ್ನು ಒದಗಿಸಿವೆ. ಪುರಾವೆ ಫಾಗಿನ್ನ 1974ರ ಪ್ರಬಂಧದ ಜೊತೆಗೆ, ಪ್ರಮೇಯದ ವಿವರವಾದ ಪುರಾವೆಯನ್ನು ಒದಗಿಸುತ್ತದೆ. ಪ್ರತಿ ಅಸ್ತಿತ್ವವಾದದ ಎರಡನೇ ಕ್ರಮಾಂಕದ ಸೂತ್ರವನ್ನು ಎನ್. ಪಿ. ಯಲ್ಲಿ ಗುರುತಿಸಬಹುದು ಎಂದು ತೋರಿಸುವುದು ಸರಳವಾಗಿದೆ, ಎಲ್ಲಾ ಅಸ್ತಿತ್ವವಾದದ-ಅರ್ಹವಾದ ಅಸ್ಥಿರಗಳ ಮೌಲ್ಯವನ್ನು ಅನಿರ್ದಿಷ್ಟವಾಗಿ ಆಯ್ಕೆ ಮಾಡುವ ಮೂಲಕ, ಆದ್ದರಿಂದ ಎನ್. ಪಿ. ಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಭಾಷೆಯನ್ನು ಅಸ್ತಿತ್ವವಾದದ ಎರಡನೇ ಕ್ರಮಾಂಕದ ಸೂತ್ರದಿಂದ ವಿವರಿಸಬಹುದು ಎಂದು ತೋರಿಸುವುದು ಪುರಾವೆಯ ಮುಖ್ಯ ಭಾಗವಾಗಿದೆ. ಹಾಗೆ ಮಾಡಲು, ಗಣನೆಯ ಟ್ಯಾಬ್ಲೋವನ್ನು ಅನಿಯಂತ್ರಿತವಾಗಿ ಆಯ್ಕೆ ಮಾಡಲು ಎರಡನೇ ಕ್ರಮಾಂಕದ ಅಸ್ತಿತ್ವವಾದದ ಕ್ವಾಂಟಿಫೈಯರ್ಗಳನ್ನು ಬಳಸಬಹುದು. ಹೆಚ್ಚು ವಿವರವಾಗಿ, ನಿರ್ಣಾಯಕವಲ್ಲದ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದ ಕಾರ್ಯಗತಗೊಳಿಸುವ ಜಾಡಿನ ಪ್ರತಿ ಸಮಯದ ಹಂತಕ್ಕೂ, ಈ ಸ್ತಬ್ಧಚಿತ್ರವು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದ ಸ್ಥಿತಿ, ಟೇಪ್ನಲ್ಲಿನ ಅದರ ಸ್ಥಾನ, ಪ್ರತಿ ಟೇಪ್ ಕೋಶದ ವಿಷಯಗಳು ಮತ್ತು ಆ ಹಂತದಲ್ಲಿ ಯಂತ್ರವು ಯಾವ ಅನಿರ್ದಿಷ್ಟ ಆಯ್ಕೆಯನ್ನು ಮಾಡುತ್ತದೆ ಎಂಬುದನ್ನು ಸಂಕೇತಿಸುತ್ತದೆ. ಮೊದಲ-ಕ್ರಮಾಂಕದ ಸೂತ್ರವು ಈ ಎನ್ಕೋಡ್ ಮಾಡಲಾದ ಮಾಹಿತಿಯನ್ನು ನಿರ್ಬಂಧಿಸಬಹುದು, ಇದರಿಂದಾಗಿ ಇದು ಮಾನ್ಯವಾದ ಕಾರ್ಯಗತಗೊಳಿಸುವ ಜಾಡಿನ ವಿವರಿಸುತ್ತದೆ, ಇದರಲ್ಲಿ ಟೇಪ್ ವಿಷಯಗಳು ಮತ್ತು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದ ಸ್ಥಿತಿ ಮತ್ತು ಪ್ರತಿ ಸಮಯದ ಹಂತದಲ್ಲಿನ ಸ್ಥಾನವು ಹಿಂದಿನ ಸಮಯದ ಹಂತದಿಂದ ಅನುಸರಿಸುತ್ತದೆ. ಪುರಾವೆಯಲ್ಲಿ ಬಳಸಲಾದ ಒಂದು ಪ್ರಮುಖ ಸೂತ್ರವೆಂದರೆ, ಬ್ರಹ್ಮಾಂಡದ ಸಂಬಂಧವಾಗಿ ಉದ್ದದ ರೇಖೀಯ ಕ್ರಮವನ್ನು (ಯಾವುದೇ ಸಮಯದ ಹಂತದಲ್ಲಿ ಸಮಯದ ಹಂತಗಳು ಮತ್ತು ಟೇಪ್ ವಿಷಯಗಳ ರೇಖೀಯ ಕ್ರಮಗಳು) ಎನ್ಕೋಡ್ ಮಾಡಲು ಸಾಧ್ಯವಿದೆ.