EXPSPACE
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಘಾತೀಯ ಜಾಗದಲ್ಲಿ ನಿರ್ಣಾಯಕ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಪರಿಹರಿಸಬಹುದಾದ ಎಲ್ಲಾ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳ ಗುಂಪಾಗಿದೆ, ಅಂದರೆ, ಬಾಹ್ಯಾಕಾಶದಲ್ಲಿ, ಅಲ್ಲಿ ಒಂದು ಬಹುಪದ ಕಾರ್ಯವಾಗಿದೆ. ಕೆಲವು ಲೇಖಕರು ರೇಖೀಯ ಕಾರ್ಯವೆಂದು ನಿರ್ಬಂಧಿಸುತ್ತಾರೆ, ಆದರೆ ಹೆಚ್ಚಿನ ಲೇಖಕರು ಅದರ ಬದಲಿಗೆ ಫಲಿತಾಂಶದ ವರ್ಗವನ್ನು ಕರೆಯುತ್ತಾರೆ. ಬದಲಿಗೆ ನಾವು ಅನಿರ್ದಿಷ್ಟ ಯಂತ್ರವನ್ನು ಬಳಸಿದರೆ, ನಾವು ವರ್ಗವನ್ನು ಪಡೆಯುತ್ತೇವೆ, ಇದು ಸಾವಿಚ್ನ ಪ್ರಮೇಯಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ಒಂದು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯೆಂದರೆ ಅದು ಒಳಗೆ ಇದ್ದರೆ, ಮತ್ತು ಒಳಗೆ ಇರುವ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆಯು ಬಹುಪದ-ಸಮಯದ ಅನೇಕ-ಒಂದು ಕಡಿತವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಬಹುಪದ-ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ ಇದೆ, ಅದು ಒಂದೇ ಉತ್ತರದೊಂದಿಗೆ ಒಂದರ ನಿದರ್ಶನಗಳನ್ನು ಇನ್ನೊಂದರ ನಿದರ್ಶನಗಳಾಗಿ ಪರಿವರ್ತಿಸುತ್ತದೆ. ಸಮಸ್ಯೆಗಳನ್ನು ಅತ್ಯಂತ ಕಠಿಣ ಸಮಸ್ಯೆಗಳೆಂದು ಪರಿಗಣಿಸಬಹುದು. ಇದು ಕಟ್ಟುನಿಟ್ಟಾದ ಸೂಪರ್ಸೆಟ್ ಆಗಿದೆ, ಮತ್ತು ಇದು ಕಟ್ಟುನಿಟ್ಟಾದ ಸೂಪರ್ಸೆಟ್ ಎಂದು ನಂಬಲಾಗಿದೆ. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನ ಮತ್ತು, ಸಮಸ್ಯೆಗಳ ಉದಾಹರಣೆಗಳು ಎರಡು ನಿಯಮಿತ ಅಭಿವ್ಯಕ್ತಿಗಳು ವಿಭಿನ್ನ ಭಾಷೆಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆಯೇ ಎಂಬುದನ್ನು ಗುರುತಿಸುವ ಸಮಸ್ಯೆಯು ಒಂದು ಸಮಸ್ಯೆಯ ಉದಾಹರಣೆಯಾಗಿದೆ, ಅಲ್ಲಿ ಅಭಿವ್ಯಕ್ತಿಗಳು ನಾಲ್ಕು ನಿರ್ವಾಹಕರಿಗೆ ಸೀಮಿತವಾಗಿವೆಃ ಒಕ್ಕೂಟ, ಸಂಯೋಜನೆ, ಕ್ಲೈನ್ ಸ್ಟಾರ್ (ಅಭಿವ್ಯಕ್ತಿಯ ಶೂನ್ಯ ಅಥವಾ ಹೆಚ್ಚಿನ ಪ್ರತಿಗಳು), ಮತ್ತು ವರ್ಗ (ಅಭಿವ್ಯಕ್ತಿಯ ಎರಡು ಪ್ರತಿಗಳು). ಕ್ಲೈನ್ ನಕ್ಷತ್ರವನ್ನು ಬಿಟ್ಟುಬಿಟ್ಟರೆ, ಆ ಸಮಸ್ಯೆಯು, ಅದನ್ನು ನಿರ್ಣಾಯಕವಲ್ಲದ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರಗಳ ಪರಿಭಾಷೆಯಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿರುವುದನ್ನು ಹೊರತುಪಡಿಸಿ, ಹಾಗೆ ಆಗುತ್ತದೆ. ಜೋಡಣೆ ಮತ್ತು ಹೋಲಿಕೆಯನ್ನು ಮಾತ್ರ ಒಳಗೊಂಡಿರುವ (ಆದರೆ ಯಾವುದೇ ಗುಣಾಕಾರವಿಲ್ಲ) ನೈಜ ಸಂಖ್ಯೆಗಳ ಬಗ್ಗೆ ಯಾವುದೇ ಪ್ರಥಮ ಕ್ರಮಾಂಕದ ಹೇಳಿಕೆಯನ್ನು ಪರಿಶೀಲಿಸುವ/ತಪ್ಪಾಗಿ ನಿರೂಪಿಸುವ ಸಮಸ್ಯೆ ಇದೆ ಎಂದು 1980ರಲ್ಲಿ ಎಲ್. ಬರ್ಮನ್ ತೋರಿಸಿದ್ದಾರೆ. ಅಲೂರ್ ಮತ್ತು ಹೆನ್ಜಿಂಗರ್ ಸಮಯಗಳೊಂದಿಗೆ (ಪೂರ್ಣಾಂಕ) ರೇಖೀಯ ತಾತ್ಕಾಲಿಕ ತರ್ಕವನ್ನು ವಿಸ್ತರಿಸಿದರು ಮತ್ತು ಅವರ ತರ್ಕದ ಸಿಂಧುತ್ವದ ಸಮಸ್ಯೆಯು EXPSPACE-ಕಂಪ್ಲೀಟ್ ಎಂದು ಸಾಬೀತುಪಡಿಸಿದರು. ಪೆಟ್ರಿ ನೆಟ್ಸ್ನ ವ್ಯಾಪ್ತಿ ಸಮಸ್ಯೆಯು-ಪೂರ್ಣವಾಗಿದೆ. ಪೆಟ್ರಿ ಬಲೆಗಳ ತಲುಪುವಿಕೆಯ ಸಮಸ್ಯೆಯು ದೀರ್ಘಕಾಲದವರೆಗೆ ಕಠಿಣವಾಗಿದೆ ಎಂದು ತಿಳಿದುಬಂದಿದೆ, ಆದರೆ ಪೂರಕವಾಗಿಲ್ಲ ಎಂದು ತೋರಿಸಲಾಗಿದೆ, ಆದ್ದರಿಂದ ಅದು ಬಹುಶಃ ಇಲ್ಲ. ಇತರ ವರ್ಗಗಳೊಂದಿಗಿನ ಸಂಬಂಧವು, ಮತ್ತು ನ ಕಟ್ಟುನಿಟ್ಟಾದ ಸೂಪರ್ಸೆಟ್ ಎಂದು ತಿಳಿದುಬಂದಿದೆ. ಇದು ಕಟ್ಟುನಿಟ್ಟಾದ ಸೂಪರ್ಸೆಟ್ ಎಂದು ಶಂಕಿಸಲಾಗಿದೆ, ಆದಾಗ್ಯೂ ಇದು ತಿಳಿದಿಲ್ಲ. ಗೇಮ್ ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ರೆಫೆರೆನ್ಸ್ ವಿಭಾಗ 9.1.1: ಎಕ್ಸ್ಪೋನೆನ್ಷಿಯಲ್ ಸ್ಪೇಸ್ ಕಂಪ್ಲೀಟೆನೆಸ್, ಪುಟಗಳು. 313-317 ಅನ್ನು ಸಹ ನೋಡಿ. ಘಾತಾಂಕದೊಂದಿಗೆ ನಿಯಮಿತ ಅಭಿವ್ಯಕ್ತಿಗಳ ಸಮಾನತೆಯನ್ನು ನಿರ್ಧರಿಸುವುದು EXPSPACE-ಕಂಪ್ಲೀಟ್ ಎಂದು ತೋರಿಸುತ್ತದೆ. ಸಂಕೀರ್ಣತೆ ತರಗತಿಗಳು