EXPTIME
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಸಂಕೀರ್ಣತೆ ವರ್ಗ EXPTIME (ಕೆಲವೊಮ್ಮೆ EXP ಅಥವಾ DEXPTIME ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ) ಘಾತೀಯ ಸಮಯದಲ್ಲಿ ನಿರ್ಣಾಯಕ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಪರಿಹರಿಸಬಹುದಾದ ಎಲ್ಲಾ ನಿರ್ಧಾರ ಸಮಸ್ಯೆಗಳ ಗುಂಪಾಗಿದೆ, ಅಂದರೆ, O (2p (n) ಸಮಯದಲ್ಲಿ, ಅಲ್ಲಿ p (n) ಎಂಬುದು n ನ ಬಹುಪದ ಕಾರ್ಯವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ವರ್ಗ 2-ಎಕ್ಸ್ಪಿಟಿಐಎಂಇ ಅನ್ನು ಎಕ್ಸ್ಪಿಟಿಐಎಂಇಗೆ ಹೋಲುತ್ತದೆ ಆದರೆ ದ್ವಿಗುಣ ಘಾತೀಯ ಸಮಯದ ಮಿತಿಯೊಂದಿಗೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಇದನ್ನು ಉನ್ನತ ಮತ್ತು ಉನ್ನತ ಸಮಯದ ಮಿತಿಗಳಿಗೆ ಸಾಮಾನ್ಯೀಕರಿಸಬಹುದು. ಬಹುಪದೀಯ ಜಾಗದಲ್ಲಿ ಪರ್ಯಾಯ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಪರಿಹರಿಸಬಹುದಾದ ಎಲ್ಲಾ ಸಮಸ್ಯೆಗಳ ಸಮೂಹವಾದ ಸ್ಪೇಸ್ ಕ್ಲಾಸ್ ಎ. ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಎಂದು ಎ. ಎಕ್ಸ್. ಪಿ. ಟಿ. ಐ. ಎಂ. ಇ. ಅನ್ನು ಮರುರೂಪಿಸಬಹುದು. EXPTIME ಇತರ ಮೂಲ ಸಮಯ ಮತ್ತು ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗಗಳಿಗೆ ಈ ಕೆಳಗಿನ ರೀತಿಯಲ್ಲಿ ಸಂಬಂಧಿಸಿದೆಃ P-NP-PSSPACE-EXPTIME-NEXPTIME-EXPSSPACE. ಇದಲ್ಲದೆ, ಸಮಯದ ಕ್ರಮಾನುಗತ ಪ್ರಮೇಯ ಮತ್ತು ಬಾಹ್ಯಾಕಾಶ ಕ್ರಮಾನುಗತ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಪಿ. ಎಕ್ಸ್. ಪಿ. ಟಿ. ಐ. ಎಂ. ಇ., ಎನ್. ಪಿ. ಎಕ್ಸ್. ಪಿ. ಟಿ. ಐ. ಎಂ. ಇ. ಮತ್ತು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಎಕ್ಸ್. ಪಿ. ಎಸ್. ಪಿ. ಎಸ್. ಇ. ಎಂದು ತಿಳಿದಿದೆ. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನ ಡಿ. ಟಿ. ಐ. ಎಂ. ಇ. ಗೆ ಸಂಬಂಧಿಸಿದಂತೆ, ಇತರ ವರ್ಗಗಳೊಂದಿಗಿನ ಸಂಬಂಧಗಳು ಸಮಯದ ಕ್ರಮಾನುಗತ ಪ್ರಮೇಯ ಮತ್ತು ಬಾಹ್ಯಾಕಾಶ ಕ್ರಮಾನುಗತ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಮೇಲಿನ ಅಭಿವ್ಯಕ್ತಿಗಳಲ್ಲಿ, ಚಿಹ್ನೆ ಎಂದರೆ "ಒಂದು ಉಪಗುಂಪು", ಮತ್ತು ಚಿಹ್ನೆ ಎಂದರೆ "ಒಂದು ಕಟ್ಟುನಿಟ್ಟಾದ ಉಪಗುಂಪು". ಆದ್ದರಿಂದ ಮೊದಲ ಮೂರು ಸೇರ್ಪಡೆಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಒಂದು ಮತ್ತು ಕೊನೆಯ ಮೂರು ಸೇರ್ಪಡೆಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಒಂದು ಸೂಕ್ತವಾಗಿರಬೇಕು, ಆದರೆ ಅವುಗಳಲ್ಲಿ ಯಾವುದು ಎಂಬುದು ತಿಳಿದಿಲ್ಲ. ಹೆಚ್ಚಿನ ತಜ್ಞರು ಎಲ್ಲಾ ಸೇರ್ಪಡೆಗಳು ಸರಿಯಾಗಿವೆ ಎಂದು ನಂಬುತ್ತಾರೆ. P = NP ಆಗಿದ್ದರೆ, ಅನಿರ್ದಿಷ್ಟ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಘಾತೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದಾದ ಸಮಸ್ಯೆಗಳ ವರ್ಗವಾದ EXPTIME NEXPTIME ಎಂದು ಸಹ ತಿಳಿದಿದೆ. ಹೆಚ್ಚು ನಿಖರವಾಗಿ ಹೇಳುವುದಾದರೆ, ಎನ್. ಪಿ. ಯಲ್ಲಿ ಪಿ. ನಲ್ಲಿಲ್ಲದ ವಿರಳ ಭಾಷೆಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ ಮತ್ತು ಇದ್ದರೆ ಮಾತ್ರ ಎಕ್ಸ್ಪೆಟೈಮ್ ಅನ್ನು ಸ್ಪೇಸ್ ಕ್ಲಾಸ್ ಎ. ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಎಂದು ಮರುರೂಪಿಸಬಹುದು, ಬಹುಪದ ಜಾಗದಲ್ಲಿ ಪರ್ಯಾಯ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಪರಿಹರಿಸಬಹುದಾದ ಎಲ್ಲಾ ಸಮಸ್ಯೆಗಳ ಸಮೂಹವಾಗಿದೆ. ಪರ್ಯಾಯ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರವು ಕನಿಷ್ಠ ಒಂದು ನಿರ್ಣಾಯಕ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಷ್ಟು ಶಕ್ತಿಯುತವಾಗಿರುವುದರಿಂದ, ಅದು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಎಕ್ಸ್. ಪಿ. ಟಿ. ಐ. ಎಂ. ಎಂದು ನೋಡಲು ಇದು ಒಂದು ಮಾರ್ಗವಾಗಿದೆ. ಎಕ್ಸ್ಪೆಟಿಐಎಂ-ಕಂಪ್ಲೀಟ್ ಒಂದು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯು ಎಕ್ಸ್ಪೆಟಿಐಎಂನಲ್ಲಿದ್ದರೆ ಅದು ಎಕ್ಸ್ಪೆಟಿಐಎಂ-ಕಂಪ್ಲೀಟ್ ಆಗಿರುತ್ತದೆ ಮತ್ತು ಎಕ್ಸ್ಪೆಟಿಐಎಂನಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆಯು ಅದಕ್ಕೆ ಬಹುಪದ-ಸಮಯದ ಅನೇಕ-ಒಂದು ಕಡಿತವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಬಹುಪದ-ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ ಇದೆ, ಅದು ಒಂದೇ ಉತ್ತರದೊಂದಿಗೆ ಒಂದರ ನಿದರ್ಶನಗಳನ್ನು ಇನ್ನೊಂದರ ನಿದರ್ಶನಗಳಾಗಿ ಪರಿವರ್ತಿಸುತ್ತದೆ. ಎಕ್ಸ್ಟಿಪಿಟಿಐಎಂಇ-ಪೂರ್ಣವಾಗಿರುವ ಸಮಸ್ಯೆಗಳನ್ನು ಎಕ್ಸ್ಟಿಪಿಟಿಐಎಂಇನಲ್ಲಿ ಅತ್ಯಂತ ಕಠಿಣವಾದ ಸಮಸ್ಯೆಗಳೆಂದು ಪರಿಗಣಿಸಬಹುದು. NP ಯು P ಗೆ ಸಮನಾಗಿರುತ್ತದೆಯೇ ಎಂಬುದು ತಿಳಿದಿಲ್ಲವಾದರೂ, EXPTIME-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಗಳು P ನಲ್ಲಿಲ್ಲ ಎಂದು ನಮಗೆ ತಿಳಿದಿದೆ; ಈ ಸಮಸ್ಯೆಗಳನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ, ಸಮಯದ ಕ್ರಮಾನುಗತ ಪ್ರಮೇಯದಿಂದ ಪರಿಹರಿಸಲಾಗುವುದಿಲ್ಲ ಎಂದು ಸಾಬೀತಾಗಿದೆ. ಗಣನೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ನಿರ್ಧರಿಸಲಾಗದ ಮೂಲಭೂತ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಒಂದು ನಿಲುಗಡೆ ಸಮಸ್ಯೆಯಾಗಿದೆಃ ನಿರ್ಣಾಯಕ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರವು (ಡಿಟಿಎಂ) ನಿಲ್ಲುತ್ತದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು. ಅತ್ಯಂತ ಮೂಲಭೂತವಾದ EXPTIME-ಪೂರ್ಣ ಸಮಸ್ಯೆಯೆಂದರೆ ಇದರ ಸರಳವಾದ ಆವೃತ್ತಿಯಾಗಿದ್ದು, ಇದು ಡಿಟಿಎಂ ಒಂದು ನಿರ್ದಿಷ್ಟ ಇನ್ಪುಟ್ ಅನ್ನು ಗರಿಷ್ಠ ಕೆ ಹಂತಗಳಲ್ಲಿ ನಿಲ್ಲಿಸುತ್ತದೆಯೇ ಎಂದು ಕೇಳುತ್ತದೆ. ಇದು EXPTIME ನಲ್ಲಿದೆ ಏಕೆಂದರೆ ಕ್ಷುಲ್ಲಕ ಸಿಮ್ಯುಲೇಶನ್ಗೆ O (k) ಸಮಯ ಬೇಕಾಗುತ್ತದೆ, ಮತ್ತು ಇನ್ಪುಟ್ k ಅನ್ನು O (log k) ಬಿಟ್ಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಎನ್ಕೋಡ್ ಮಾಡಲಾಗುತ್ತದೆ, ಇದು ಘಾತೀಯ ಸಂಖ್ಯೆಯ ಸಿಮ್ಯುಲೇಶನ್ಗಳಿಗೆ ಕಾರಣವಾಗುತ್ತದೆ. ಇದು ಎಕ್ಸಿಪ್ಟೈಮ್-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ ಏಕೆಂದರೆ, ಸ್ಥೂಲವಾಗಿ ಹೇಳುವುದಾದರೆ, ಎಕ್ಸಿಪ್ಟೈಮ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಯಂತ್ರವು ಘಾತೀಯ ಸಂಖ್ಯೆಯ ಹಂತಗಳಲ್ಲಿ ಸ್ವೀಕರಿಸುತ್ತದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸಲು ನಾವು ಇದನ್ನು ಬಳಸಬಹುದು; ಅದು ಹೆಚ್ಚು ಬಳಸುವುದಿಲ್ಲ. ಯುನೇರಿಯಲ್ಲಿ ಬರೆಯಲಾದ ಹಂತಗಳ ಸಂಖ್ಯೆಯೊಂದಿಗಿನ ಅದೇ ಸಮಸ್ಯೆಯು ಪಿ-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ. EXPTIME-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳ ಇತರ ಉದಾಹರಣೆಗಳಲ್ಲಿ ಸಾಮಾನ್ಯೀಕೃತ ಚೆಸ್, ಚೆಕರ್ಸ್ ಅಥವಾ ಗೋ (ಜಪಾನೀಸ್ ಕೋ ನಿಯಮಗಳೊಂದಿಗೆ) ನಲ್ಲಿ ಸ್ಥಾನವನ್ನು ಮೌಲ್ಯಮಾಪನ ಮಾಡುವ ಸಮಸ್ಯೆ ಸೇರಿದೆ. ಈ ಆಟಗಳು ಎಕ್ಸ್ಪೆಟಿಐಎಂಇ-ಪೂರ್ಣಗೊಳ್ಳುವ ಅವಕಾಶವನ್ನು ಹೊಂದಿವೆ ಏಕೆಂದರೆ ಆಟಗಳು ಫಲಕದ ಗಾತ್ರದಲ್ಲಿ ಘಾತೀಯವಾದ ಹಲವಾರು ಚಲನೆಗಳಿಗೆ ಉಳಿಯಬಹುದು. ಗೋ ಉದಾಹರಣೆಯಲ್ಲಿ, ಜಪಾನಿನ ಕೋ ನಿಯಮವು ಎಕ್ಸ್ಪ್ಟಿಮ್-ಕಂಪ್ಲೀಟೆನೆಸ್ ಅನ್ನು ಸೂಚಿಸುತ್ತದೆ ಎಂದು ತಿಳಿದುಬಂದಿದೆ, ಆದರೆ ಆಟದ ಅಮೇರಿಕನ್ ಅಥವಾ ಚೀನೀ ನಿಯಮಗಳು ಎಕ್ಸ್ಪ್ಟಿಮ್-ಕಂಪ್ಲೀಟ್ ಆಗಿವೆಯೇ ಎಂಬುದು ತಿಳಿದಿಲ್ಲ (ಅವು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ ಯಿಂದ ಎಕ್ಸ್ಪೇಸ್ ವರೆಗೆ ಇರಬಹುದು). ಇದಕ್ಕೆ ವ್ಯತಿರಿಕ್ತವಾಗಿ, ಫಲಕದ ಗಾತ್ರದಲ್ಲಿ ಬಹುಪದವಾಗಿರುವ ಹಲವಾರು ಚಲನೆಗಳಿಗೆ ಉಳಿಯುವ ಸಾಮಾನ್ಯೀಕೃತ ಆಟಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣವಾಗಿರುತ್ತವೆ. ಪುನರಾವರ್ತನೆಯಾಗದ ಆಟಗಳು ಸ್ವಯಂಚಾಲಿತವಾಗಿರುವ ಘಾತೀಯವಾಗಿ ದೀರ್ಘವಾದ ಆಟಗಳಿಗೂ ಇದು ಅನ್ವಯಿಸುತ್ತದೆ. ಪ್ರಮುಖ EXPTIME-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳ ಮತ್ತೊಂದು ಗುಂಪು ಸಂಕ್ಷಿಪ್ತ ಸರ್ಕ್ಯೂಟ್ಗಳಿಗೆ ಸಂಬಂಧಿಸಿದೆ. ಸ್ಯೂಸಿಂಕ್ಟ್ ಸರ್ಕ್ಯೂಟ್ಗಳು ಕೆಲವು ಗ್ರಾಫ್ಗಳನ್ನು ಘಾತೀಯವಾಗಿ ಕಡಿಮೆ ಜಾಗದಲ್ಲಿ ವಿವರಿಸಲು ಬಳಸುವ ಸರಳ ಯಂತ್ರಗಳಾಗಿವೆ. ಅವು ಎರಡು ಶೃಂಗ ಸಂಖ್ಯೆಗಳನ್ನು ಅವುಗಳ ನಡುವೆ ಅಂಚು ಇದೆಯೇ ಎಂಬುದನ್ನು ಇನ್ಪುಟ್ ಮತ್ತು ಔಟ್ಪುಟ್ ಆಗಿ ಸ್ವೀಕರಿಸುತ್ತವೆ. ಅನೇಕ ನೈಸರ್ಗಿಕ ಪಿ-ಕಂಪ್ಲೀಟ್ ಗ್ರಾಫ್ ಸಮಸ್ಯೆಗಳಿಗೆ, ಅಲ್ಲಿ ಗ್ರಾಫ್ ಅನ್ನು ಸಮೀಪದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನಂತಹ ನೈಸರ್ಗಿಕ ಪ್ರಾತಿನಿಧ್ಯದಲ್ಲಿ ವ್ಯಕ್ತಪಡಿಸಲಾಗುತ್ತದೆ, ಸಂಕ್ಷಿಪ್ತ ಸರ್ಕ್ಯೂಟ್ ಪ್ರಾತಿನಿಧ್ಯದಲ್ಲಿ ಅದೇ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವುದು ಎಕ್ಸ್ಟಿಪಿಟಿಐಎಂಇ-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ, ಏಕೆಂದರೆ ಇನ್ಪುಟ್ ಘಾತೀಯವಾಗಿ ಚಿಕ್ಕದಾಗಿದೆ; ಆದರೆ ಇದಕ್ಕೆ ಅಲ್ಪವಲ್ಲದ ಪುರಾವೆಯ ಅಗತ್ಯವಿರುತ್ತದೆ, ಏಕೆಂದರೆ ಸಂಕ್ಷಿಪ್ತ ಸರ್ಕ್ಯೂಟ್ಗಳು ಗ್ರಾಫ್ಗಳ ಉಪವರ್ಗವನ್ನು ಮಾತ್ರ ವಿವರಿಸಬಹುದು. ಉಲ್ಲೇಖಗಳ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗಗಳು