Structural complexity theory
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ರಚನಾತ್ಮಕ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತ ಅಥವಾ ಸರಳವಾಗಿ ರಚನಾತ್ಮಕ ಸಂಕೀರ್ಣತೆಯು ವೈಯಕ್ತಿಕ ಸಮಸ್ಯೆಗಳು ಮತ್ತು ಕ್ರಮಾವಳಿಗಳ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಗಿಂತ ಹೆಚ್ಚಾಗಿ ಸಂಕೀರ್ಣತೆ ವರ್ಗಗಳ ಅಧ್ಯಯನವಾಗಿದೆ. ಇದು ವಿವಿಧ ಸಂಕೀರ್ಣತೆ ವರ್ಗಗಳ ಆಂತರಿಕ ರಚನೆಗಳು ಮತ್ತು ವಿಭಿನ್ನ ಸಂಕೀರ್ಣತೆ ವರ್ಗಗಳ ನಡುವಿನ ಸಂಬಂಧಗಳೆರಡರ ಸಂಶೋಧನೆಯನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಈ ರೀತಿಯ ಮೊದಲ ಮತ್ತು ಇನ್ನೂ ಪ್ರಮುಖವಾದ ಪ್ರಶ್ನೆಯಾದ ಪಿ = ಎನ್. ಪಿ. ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ (ಇನ್ನೂ ವಿಫಲವಾದ) ಪ್ರಯತ್ನಗಳ ಪರಿಣಾಮವಾಗಿ ಈ ಸಿದ್ಧಾಂತವು ಹೊರಹೊಮ್ಮಿದೆ. ಹೆಚ್ಚಿನ ಸಂಶೋಧನೆಗಳನ್ನು ಪಿ ಎನ್ಪಿಗೆ ಸಮನಾಗಿಲ್ಲ ಎಂಬ ಊಹೆಯ ಆಧಾರದ ಮೇಲೆ ಮತ್ತು ಸಂಕೀರ್ಣತೆಯ ವರ್ಗಗಳ ಬಹುಪದ ಸಮಯದ ಶ್ರೇಣಿಯು ಅನಂತವಾಗಿದೆ ಎಂಬ ಹೆಚ್ಚು ದೂರಗಾಮಿ ಊಹೆಯ ಆಧಾರದ ಮೇಲೆ ಮಾಡಲಾಗುತ್ತದೆ. ಪ್ರಮುಖ ಫಲಿತಾಂಶಗಳು ಸಂಕೋಚನ ಪ್ರಮೇಯ ಸಂಕೋಚನ ಪ್ರಮೇಯವು ಗಣನೆಯ ಕಾರ್ಯಗಳ ಸಂಕೀರ್ಣತೆಯ ಬಗ್ಗೆ ಒಂದು ಪ್ರಮುಖ ಪ್ರಮೇಯವಾಗಿದೆ. ಎಲ್ಲಾ ಗಣಿಸಬಹುದಾದ ಕಾರ್ಯಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಗಣಿಸಬಹುದಾದ ಗಡಿಯೊಂದಿಗೆ ಯಾವುದೇ ದೊಡ್ಡ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗ ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲ ಎಂದು ಪ್ರಮೇಯವು ಹೇಳುತ್ತದೆ. ಬಾಹ್ಯಾಕಾಶ ಕ್ರಮಾನುಗತ ಪ್ರಮೇಯಗಳು ಬಾಹ್ಯಾಕಾಶ ಕ್ರಮಾನುಗತ ಪ್ರಮೇಯಗಳು ಕೆಲವು ಷರತ್ತುಗಳಿಗೆ ಒಳಪಟ್ಟು, ನಿರ್ಣಾಯಕ ಮತ್ತು ಅನಿರ್ದಿಷ್ಟ ಯಂತ್ರಗಳೆರಡೂ ಹೆಚ್ಚಿನ ಜಾಗವನ್ನು (ಲಕ್ಷಣರಹಿತವಾಗಿ) ಪರಿಹರಿಸಬಲ್ಲವು ಎಂಬುದನ್ನು ತೋರಿಸುವ ಪ್ರತ್ಯೇಕತೆಯ ಫಲಿತಾಂಶಗಳಾಗಿವೆ. ಉದಾಹರಣೆಗೆ, ಒಂದು ನಿರ್ಣಾಯಕ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರವು ಬಾಹ್ಯಾಕಾಶ n ಗಿಂತ ಬಾಹ್ಯಾಕಾಶ n ನಲ್ಲಿ ಹೆಚ್ಚಿನ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಬಲ್ಲದು. ಸಮಯ ಶ್ರೇಣಿ ವ್ಯವಸ್ಥೆಗಳು ಸಮಯ ಶ್ರೇಣಿ ವ್ಯವಸ್ಥೆಗಳು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರಗಳ ಮೇಲೆ ಸಮಯ-ಮಿತಿಯ ಗಣನೆಯ ಬಗ್ಗೆ ಪ್ರಮುಖ ಹೇಳಿಕೆಗಳಾಗಿವೆ. ಅನೌಪಚಾರಿಕವಾಗಿ, ಈ ಪ್ರಮೇಯಗಳು ಹೆಚ್ಚಿನ ಸಮಯವನ್ನು ನೀಡಿದರೆ, ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರವು ಹೆಚ್ಚಿನ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಬಹುದು ಎಂದು ಹೇಳುತ್ತವೆ. ಉದಾಹರಣೆಗೆ, n2 ಸಮಯದೊಂದಿಗೆ ಪರಿಹರಿಸಬಹುದಾದ ಸಮಸ್ಯೆಗಳಿವೆ ಆದರೆ n ಸಮಯದೊಂದಿಗೆ ಅಲ್ಲ. ವಾಲಿಯಂಟ್-ವಜೀರಾನಿ ಪ್ರಮೇಯವು ಗಣನೆಯ ಸಂಕೀರ್ಣತೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಒಂದು ಪ್ರಮೇಯವಾಗಿದೆ. ಇದನ್ನು ಲೆಸ್ಲಿ ವಾಲಿಯಂಟ್ ಮತ್ತು ವಿಜಯ್ ವಜೀರಾನಿ ಅವರು 1986ರಲ್ಲಿ ಪ್ರಕಟವಾದ ಎನ್. ಪಿ. ಎಂಬ ಶೀರ್ಷಿಕೆಯ ತಮ್ಮ ಪ್ರಬಂಧದಲ್ಲಿ, ಅನನ್ಯ ಪರಿಹಾರಗಳನ್ನು ಪತ್ತೆಹಚ್ಚುವಷ್ಟು ಸುಲಭ ಎಂದು ಸಾಬೀತುಪಡಿಸಿದ್ದಾರೆ. ಅಸಂದಿಗ್ಧ-ಎಸ್. ಎ. ಟಿ. ಗೆ ಬಹುಪದ ಸಮಯದ ಕ್ರಮಾವಳಿ ಇದ್ದರೆ, ಆಗ ಎನ್. ಪಿ. = ಆರ್. ಪಿ. ಎಂದು ಪ್ರಮೇಯವು ಹೇಳುತ್ತದೆ. ಪುರಾವೆಯು ಮುಲ್ಮುಲೆ-ವಜೀರಾನಿ ಪ್ರತ್ಯೇಕ ಲೆಮ್ಮಾವನ್ನು ಆಧರಿಸಿದೆ, ಇದನ್ನು ತರುವಾಯ ಸೈದ್ಧಾಂತಿಕ ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ ಹಲವಾರು ಪ್ರಮುಖ ಅನ್ವಯಿಕೆಗಳಿಗೆ ಬಳಸಲಾಯಿತು. ಸಿಪ್ಸರ್-ಲೌಟೆಮನ್ ಪ್ರಮೇಯ ಸಿಪ್ಸರ್-ಲೌಟೆಮನ್ ಪ್ರಮೇಯ ಅಥವಾ ಸಿಪ್ಸರ್-ಗಾಕ್ಸ್-ಲೌಟೆಮನ್ ಪ್ರಮೇಯವು ಬೌಂಡೇಡ್-ಎರರ್ ಪ್ರೋಬಬಿಲಿಸ್ಟಿಕ್ ಪೊಲಿನೋಮಿಯಲ್ (ಬಿಪಿಪಿ) ಸಮಯವು ಬಹುಪದೀಯ ಸಮಯದ ಶ್ರೇಣಿಯಲ್ಲಿ ಮತ್ತು ಹೆಚ್ಚು ನಿರ್ದಿಷ್ಟವಾಗಿ σ2 θ Π2ನಲ್ಲಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. 1970 ರಲ್ಲಿ ವಾಲ್ಟರ್ ಸಾವಿಚ್ ಅವರು ಸಾಬೀತುಪಡಿಸಿದ ಸಾವಿಚ್ ಅವರ ಪ್ರಮೇಯವು ನಿರ್ಣಾಯಕ ಮತ್ತು ನಿರ್ಣಾಯಕವಲ್ಲದ ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯ ನಡುವಿನ ಸಂಬಂಧವನ್ನು ನೀಡುತ್ತದೆ. ಯಾವುದೇ ಕಾರ್ಯಕ್ಕಾಗಿ, ತೋಡಾ ಅವರ ಪ್ರಮೇಯವು ಸಿನೋಸುಕೆ ತೋಡಾ ಅವರು ತಮ್ಮ ಪ್ರಬಂಧ "ಪಿಪಿ ಈಸ್ ಆಸ್ ಹಾರ್ಡ್ ಆಸ್ ದಿ ಪೊಲಿನೋಮಿಯಲ್-ಟೈಮ್ ಹೈರಾರ್ಕಿ" (1991) ಯಲ್ಲಿ ಸಾಬೀತುಪಡಿಸಿದ ಫಲಿತಾಂಶವಾಗಿದೆ ಮತ್ತು 1998ರ ಗೊಡೆಲ್ ಪ್ರಶಸ್ತಿಯನ್ನು ನೀಡಲಾಯಿತು ಎಂದು ಅದು ಹೇಳುತ್ತದೆ. ಸಂಪೂರ್ಣ ಬಹುಪದೀಯ ಕ್ರಮಾನುಗತ ಪಿಎಚ್ ಅನ್ನು ಪಿಪಿಪಿ ಹೊಂದಿದೆ ಎಂದು ಪ್ರಮೇಯವು ಹೇಳುತ್ತದೆ; ಇದು ಪಿಎಚ್ ಅನ್ನು P#P ನಲ್ಲಿದೆ ಎಂಬ ನಿಕಟವಾದ ಸಂಬಂಧಿತ ಹೇಳಿಕೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಇಮ್ಮರ್ಮನ್-ಸ್ಜೆಲೆಪ್ಸೆನಿ ಪ್ರಮೇಯವನ್ನು 1987 ರಲ್ಲಿ ನೀಲ್ ಇಮ್ಮರ್ಮನ್ ಮತ್ತು ರಾಬರ್ಟ್ ಸ್ಜೆಲೆಪ್ಸೆನಿ ಅವರು ಸ್ವತಂತ್ರವಾಗಿ ಸಾಬೀತುಪಡಿಸಿದರು, ಇದಕ್ಕಾಗಿ ಅವರು 1995 ರ ಗೊಡೆಲ್ ಪ್ರಶಸ್ತಿಯನ್ನು ಹಂಚಿಕೊಂಡರು. ಅದರ ಸಾಮಾನ್ಯ ರೂಪದಲ್ಲಿ ಪ್ರಮೇಯವು ಯಾವುದೇ ಕಾರ್ಯಕ್ಕೆ ಎನ್. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. (ಎಸ್ (ಎನ್)) = ಕೋ-ಎನ್. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. (ಎಸ್ (ಎನ್)) ಎಂದು ಹೇಳುತ್ತದೆ. ಈ ಫಲಿತಾಂಶವು ಎರಡನೇ ಎಲ್. ಬಿ. ಎ. ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಿತು. ಸಂಶೋಧನಾ ವಿಷಯಗಳು ಈ ಕ್ಷೇತ್ರದಲ್ಲಿ ಸಂಶೋಧನೆಯ ಪ್ರಮುಖ ನಿರ್ದೇಶನಗಳು ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಒಳಗೊಂಡಿವೆಃ ಸಂಕೀರ್ಣತೆ ವರ್ಗಗಳ ಬಗೆಗಿನ ವಿವಿಧ ಬಗೆಹರಿಯದ ಸಮಸ್ಯೆಗಳಿಂದ ಉಂಟಾಗುವ ಪರಿಣಾಮಗಳ ಅಧ್ಯಯನ, ವಿವಿಧ ರೀತಿಯ ಸಂಪನ್ಮೂಲ-ನಿರ್ಬಂಧಿತ ಕಡಿತಗಳ ಅಧ್ಯಯನ ಮತ್ತು ದತ್ತಾಂಶದ ಸಂಗ್ರಹಣೆ ಮತ್ತು ಪ್ರವೇಶದ ಕಾರ್ಯವಿಧಾನಗಳ ಮೇಲೆ ವಿವಿಧ ನಿರ್ಬಂಧಗಳ ಪರಿಣಾಮಗಳ ಅನುಗುಣವಾದ ಸಂಪೂರ್ಣ ಭಾಷೆಗಳ ಅಧ್ಯಯನ.