PSPACE-complete
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಇನ್ಪುಟ್ ಉದ್ದದಲ್ಲಿ (ಬಹುಪದೀಯ ಸ್ಥಳ) ಬಹುಪದೀಯವಾಗಿರುವ ಮೆಮೊರಿಯ ಪ್ರಮಾಣವನ್ನು ಬಳಸಿಕೊಂಡು ಪರಿಹರಿಸಬಹುದಾದರೆ ಮತ್ತು ಬಹುಪದೀಯ ಜಾಗದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದಾದ ಪ್ರತಿಯೊಂದು ಇತರ ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಪರಿವರ್ತಿಸಬಹುದಾದರೆ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣವಾಗಿರುತ್ತದೆ. ಬಹುಪದೀಯ ಜಾಗದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದಾದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳ ವರ್ಗವಾದ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಯಲ್ಲಿ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ.-ಪೂರ್ಣವಾಗಿರುವ ಸಮಸ್ಯೆಗಳನ್ನು ಅತ್ಯಂತ ಕಠಿಣವಾದ ಸಮಸ್ಯೆಗಳೆಂದು ಪರಿಗಣಿಸಬಹುದು, ಏಕೆಂದರೆ ಅಂತಹ ಯಾವುದೇ ಒಂದು ಸಮಸ್ಯೆಗೆ ಪರಿಹಾರವನ್ನು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಯಲ್ಲಿ ಬೇರೆ ಯಾವುದೇ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಸುಲಭವಾಗಿ ಬಳಸಬಹುದು. ನಿಯಮಿತ ಅಭಿವ್ಯಕ್ತಿಗಳು ಮತ್ತು ಸಂದರ್ಭ-ಸೂಕ್ಷ್ಮ ವ್ಯಾಕರಣಗಳ ಗುಣಲಕ್ಷಣಗಳನ್ನು ನಿರ್ಧರಿಸುವುದು, ಪ್ರಮಾಣೀಕೃತ ಬೂಲಿಯನ್ ಸೂತ್ರಗಳ ಸತ್ಯವನ್ನು ನಿರ್ಧರಿಸುವುದು, ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳ ಪರಿಹಾರಗಳ ನಡುವಿನ ಹಂತ-ಹಂತದ ಬದಲಾವಣೆಗಳು ಮತ್ತು ಅನೇಕ ಒಗಟುಗಳು ಮತ್ತು ಆಟಗಳು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಕಂಪ್ಲೀಟ್ ಎಂದು ತಿಳಿದಿರುವ ಸಮಸ್ಯೆಗಳಾಗಿವೆ. ಒಂದು ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದೀಯ ಪ್ರಮಾಣದ ಮೆಮೊರಿಯನ್ನು ಬಳಸಿಕೊಂಡು ಪರಿಹರಿಸಬಹುದಾದರೆ (ಅದು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಗೆ ಸೇರಿದೆ) ಮತ್ತು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಕೊಟ್ಟಿರುವ ಸಮಸ್ಯೆಯ ಸಮಾನ ನಿದರ್ಶನವಾಗಿ ಪರಿವರ್ತಿಸಬಹುದಾದರೆ ಅದನ್ನು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ.-ಕಂಪ್ಲೀಟ್ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ.-ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆಗಳು ಹೆಚ್ಚು ಪ್ರಸಿದ್ಧವಾದ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗಗಳಾದ ಪಿ (ಬಹುಪದ ಸಮಯ) ಮತ್ತು ಎನ್. ಪಿ. (ನಿರ್ಣಾಯಕವಲ್ಲದ ಬಹುಪದ ಸಮಯ) ಗಳಿಂದ ಹೊರಗಿವೆ ಎಂದು ವ್ಯಾಪಕವಾಗಿ ಶಂಕಿಸಲಾಗಿದೆ, ಆದರೆ ಅದು ತಿಳಿದಿಲ್ಲ. ಅವು ಅತ್ಯಂತ ಪರಿಣಾಮಕಾರಿ ಸಮಾನಾಂತರ ಕ್ರಮಾವಳಿಗಳನ್ನು ಹೊಂದಿರುವ ಸಮಸ್ಯೆಗಳ ವರ್ಗವಾದ ಎನ್. ಸಿ. ಯ ಹೊರಗಿವೆ ಎಂದು ತಿಳಿದಿದೆ, ಏಕೆಂದರೆ ಎನ್. ಸಿ. ಯಲ್ಲಿನ ಸಮಸ್ಯೆಗಳನ್ನು ಇನ್ಪುಟ್ ಗಾತ್ರದ ಲಾಗರಿದಮ್ನಲ್ಲಿ ಬಾಹ್ಯಾಕಾಶ ಬಹುಪದಿಯಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು, ಮತ್ತು ಅಂತಹ ಸಣ್ಣ ಪ್ರಮಾಣದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದಾದ ಸಮಸ್ಯೆಗಳ ವರ್ಗವು ಬಾಹ್ಯಾಕಾಶ ಕ್ರಮಾನುಗತ ಪ್ರಮೇಯದಿಂದ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಯಲ್ಲಿ ಕಟ್ಟುನಿಟ್ಟಾಗಿ ಒಳಗೊಂಡಿರುತ್ತದೆ. ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಸಂಪೂರ್ಣತೆಯನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುವಲ್ಲಿ ಸಾಮಾನ್ಯವಾಗಿ ಪರಿಗಣಿಸಲಾಗುವ ರೂಪಾಂತರಗಳು ಬಹುಪದ-ಸಮಯದ ಅನೇಕ-ಒಂದು ಕಡಿತಗಳು, ಒಂದು ರೀತಿಯ ಸಮಸ್ಯೆಯ ಒಂದೇ ನಿದರ್ಶನವನ್ನು ಬೇರೆ ರೀತಿಯ ಸಮಸ್ಯೆಯ ಸಮಾನವಾದ ಒಂದೇ ನಿದರ್ಶನವಾಗಿ ತೆಗೆದುಕೊಳ್ಳುವ ರೂಪಾಂತರಗಳು. ಆದಾಗ್ಯೂ, ಟ್ಯೂರಿಂಗ್ ಕಡಿತಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಸಂಪೂರ್ಣತೆಯನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲು ಸಹ ಸಾಧ್ಯವಿದೆ, ಇದರಲ್ಲಿ ಒಂದು ಸಮಸ್ಯೆಯನ್ನು ಇತರ ಸಮಸ್ಯೆಗೆ ಬಹುಪದೀಯ ಸಂಖ್ಯೆಯ ಕರೆಗಳ ಮೂಲಕ ಪರಿಹರಿಸಬಹುದು. ಈ ಎರಡು ರೀತಿಯ ಕಡಿತಗಳು ವಿವಿಧ ವರ್ಗದ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳಿಗೆ ಕಾರಣವಾಗುತ್ತವೆಯೇ ಎಂಬುದು ತಿಳಿದಿಲ್ಲ. ಪರಿವರ್ತಿತ ಇನ್ಪುಟ್ನ ಉದ್ದವನ್ನು ಯಾವಾಗಲೂ ಹೆಚ್ಚಿಸುವ ಅನೇಕ-ಒಂದು ಕಡಿತಗಳಂತಹ ಇತರ ರೀತಿಯ ಕಡಿತಗಳನ್ನು ಸಹ ಪರಿಗಣಿಸಲಾಗಿದೆ. ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಕಂಪ್ಲೀಟ್ ಸೆಟ್ಗಳಿಗಾಗಿ ಬರ್ಮನ್-ಹಾರ್ಟ್ಮನಿಸ್ ಊಹೆಯ ಒಂದು ಆವೃತ್ತಿಯು ಅಂತಹ ಎಲ್ಲಾ ಸೆಟ್ಗಳು ಒಂದೇ ರೀತಿ ಕಾಣುತ್ತವೆ ಎಂದು ಹೇಳುತ್ತದೆ, ಅಂದರೆ ಅವೆಲ್ಲವನ್ನೂ ಬಹುಪದ-ಸಮಯದ ಬೈಜೆಕ್ಷನ್ಗಳಿಂದ ಪರಸ್ಪರ ಪರಿವರ್ತಿಸಬಹುದು. ಔಪಚಾರಿಕ ಭಾಷೆಗಳ ಉದಾಹರಣೆಗಳು ನಿಯಮಿತ ಅಭಿವ್ಯಕ್ತಿಯನ್ನು ನೀಡಿದರೆ, ಅದು ಅದರ ವರ್ಣಮಾಲೆಯ ಮೇಲೆ ಪ್ರತಿ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ. ಮೊದಲ ತಿಳಿದಿರುವ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆಯು ನಿರ್ಣಾಯಕ ಸಂದರ್ಭ-ಸೂಕ್ಷ್ಮ ವ್ಯಾಕರಣಗಳಿಗೆ ಸಂಬಂಧಿಸಿದ ಪದ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಸಂದರ್ಭ-ಸೂಕ್ಷ್ಮ ವ್ಯಾಕರಣಗಳ ಪದ ಸಮಸ್ಯೆಯಲ್ಲಿ, ವಾಕ್ಯದ ಉದ್ದವನ್ನು ಹೆಚ್ಚಿಸಬಹುದು, ಆದರೆ ಕಡಿಮೆ ಮಾಡಲು ಸಾಧ್ಯವಿಲ್ಲದ ವ್ಯಾಕರಣದ ರೂಪಾಂತರಗಳ ಗುಂಪನ್ನು ನೀಡಲಾಗುತ್ತದೆ ಮತ್ತು ಈ ರೂಪಾಂತರಗಳಿಂದ ನಿರ್ದಿಷ್ಟ ವಾಕ್ಯವನ್ನು ಉತ್ಪಾದಿಸಬಹುದೇ ಎಂದು ನಿರ್ಧರಿಸಲು ಬಯಸುತ್ತಾರೆ. "ನಿರ್ಣಾಯಕತೆ" ಯ ತಾಂತ್ರಿಕ ಸ್ಥಿತಿಯು (ಪ್ರತಿ ರೂಪಾಂತರವು ಅದನ್ನು ಬಳಸಲಾಗಿದೆ ಎಂದು ಸ್ಥೂಲವಾಗಿ ಸೂಚಿಸುತ್ತದೆ) ಈ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಬಹುಪದ ಜಾಗದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ ಮತ್ತು ರೇಖೀಯ ಜಾಗದಲ್ಲಿ ಗಣಿಸಬಹುದಾದ ಪ್ರತಿಯೊಂದು (ಪ್ರಾಯಶಃ ನಿರ್ಣಾಯಕವಲ್ಲದ) ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ಸಂದರ್ಭ-ಸೂಕ್ಷ್ಮ ವ್ಯಾಕರಣದ ಪಾರ್ಸಿಂಗ್ ಆಗಿ ಪರಿವರ್ತಿಸಬಹುದು ಎಂದು ತೋರಿಸುತ್ತದೆ, ಇದು ನಿರ್ಣಾಯಕತೆಯನ್ನು ಸಂರಕ್ಷಿಸುತ್ತದೆ. 1970 ರಲ್ಲಿ, ಸ್ಯಾವಿಚ್ನ ಪ್ರಮೇಯವು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಅನ್ನು ಅನಿರ್ದಿಷ್ಟತೆಯ ಅಡಿಯಲ್ಲಿ ಮುಚ್ಚಲಾಗಿದೆ ಎಂದು ತೋರಿಸಿತು, ಇದು ನಿರ್ಣಾಯಕವಲ್ಲದ ಸಂದರ್ಭ-ಸೂಕ್ಷ್ಮ ವ್ಯಾಕರಣಗಳು ಸಹ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ನಲ್ಲಿವೆ ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ತರ್ಕವು ಅನೇಕ ಇತರ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪರಿಪೂರ್ಣತೆಯ ಫಲಿತಾಂಶಗಳಲ್ಲಿ ಬಳಸಲಾಗುವ ಒಂದು ಪ್ರಮಾಣಿತ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣ ಸಮಸ್ಯೆಯಾಗಿದ್ದು, ಇದು ಕ್ವಾಂಟಿಫೈಡ್ ಬೂಲಿಯನ್ ಸೂತ್ರದ ಸಮಸ್ಯೆಯಾಗಿದೆ, ಇದು ಬೂಲಿಯನ್ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಯ ಸಾಮಾನ್ಯೀಕರಣವಾಗಿದೆ. ಕ್ವಾಂಟಿಫೈಡ್ ಬೂಲಿಯನ್ ಸೂತ್ರದ ಸಮಸ್ಯೆಯು ಬೂಲಿಯನ್ ಅಭಿವ್ಯಕ್ತಿಯನ್ನು ಇನ್ಪುಟ್ ಆಗಿ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಅದರ ಎಲ್ಲಾ ಅಸ್ಥಿರಗಳನ್ನು ಸಾರ್ವತ್ರಿಕವಾಗಿ ಅಥವಾ ಅಸ್ತಿತ್ವದಲ್ಲಿ ಪ್ರಮಾಣೀಕರಿಸಲಾಗುತ್ತದೆ, ಉದಾಹರಣೆಗೆಃ ಸಮಸ್ಯೆಯ ಔಟ್ಪುಟ್ ಕ್ವಾಂಟಿಫೈಡ್ ಅಭಿವ್ಯಕ್ತಿಯ ಮೌಲ್ಯವಾಗಿದೆ. ಈ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ. ಪುನಸ್ಸಂಯೋಜನೆಯ ಪುನಸ್ಸಂಯೋಜನೆಯ ಸಮಸ್ಯೆಗಳು ಒಂದು ಸಂಯೋಜಿತ ಸಮಸ್ಯೆಗೆ ಪರಿಹಾರಗಳ ಸ್ಥಿತಿಯ ಸ್ಥಳದ ಸಂಪರ್ಕಕ್ಕೆ ಸಂಬಂಧಿಸಿವೆ. ಉದಾಹರಣೆಗೆ, ಗ್ರಾಫ್ನ ಎರಡು 4-ಬಣ್ಣಗಳನ್ನು ಒಂದು ಸಮಯದಲ್ಲಿ ಒಂದು ಶೃಂಗದ ಬಣ್ಣವನ್ನು ಬದಲಾಯಿಸುವ ಚಲನೆಗಳಿಂದ ಪರಸ್ಪರ ಸಂಪರ್ಕಿಸಬಹುದೇ ಎಂದು ಪರೀಕ್ಷಿಸುವುದು, ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಮಾನ್ಯವಾದ 4-ಬಣ್ಣವನ್ನು ಕಾಪಾಡಿಕೊಳ್ಳುವುದು, 3-ಬಣ್ಣಗಳಿಗೆ ಒಂದೇ ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದಾದರೂ, ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣವಾಗಿದೆ. ಪುನರ್ರಚನೆ ಸಮಸ್ಯೆಗಳ ಮತ್ತೊಂದು ಕುಟುಂಬವು, ಈ ಪ್ರದೇಶದಲ್ಲಿನ ಇತರ ಅನೇಕ ಸಮಸ್ಯೆಗಳ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣತೆಯ ಪುರಾವೆಗಳ ಆಧಾರವಾಗಿ ಪ್ರಮಾಣೀಕರಿಸಿದ ಬೂಲಿಯನ್ ಸೂತ್ರಗಳಂತೆಯೇ ಬಳಸಲ್ಪಡುತ್ತದೆ, ಇದು ಅನಿರ್ಧಾರಣೀಯ ನಿರ್ಬಂಧದ ತರ್ಕವನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಇದರಲ್ಲಿ ಪ್ರತಿ ಶೃಂಗದಲ್ಲಿ ಎಷ್ಟು ಅಂಚುಗಳನ್ನು ಒಳಮುಖವಾಗಿ ಹೊಂದಿರಬೇಕು ಎಂಬುದರ ಮೇಲೆ ಕೆಲವು ನಿರ್ಬಂಧಗಳಿಗೆ ಒಳಪಟ್ಟು ನಿರ್ಬಂಧದ ರೇಖಾಚಿತ್ರದ ದಿಕ್ಕುಗಳನ್ನು ಸ್ಥಿತಿಗಳು ಒಳಗೊಂಡಿರುತ್ತವೆ ಮತ್ತು ಇದರಲ್ಲಿ ರಾಜ್ಯದಿಂದ ರಾಜ್ಯಕ್ಕೆ ಚಲನೆಗಳು ಒಂದೇ ಅಂಚಿನ ದಿಕ್ಕನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸುತ್ತವೆ. ಒಗಟುಗಳು ಮತ್ತು ಆಟಗಳು ಪ್ರಮಾಣೀಕರಿಸಿದ ಬೂಲಿಯನ್ ಸೂತ್ರದ ಸಮಸ್ಯೆಯನ್ನು ಇಬ್ಬರು ಆಟಗಾರರು, ಪರಿಶೀಲಿಸುವವರು ಮತ್ತು ತಪ್ಪುದಾರಿಗೆಳೆಯುವವರು ಆಟ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು. ಆಟಗಾರರು ಕ್ವಾಂಟಿಫೈಡ್ ವೇರಿಯೇಬಲ್ಗಳಿಗೆ ಮೌಲ್ಯಗಳನ್ನು ತುಂಬುವ ಚಲನೆಗಳನ್ನು ಮಾಡುತ್ತಾರೆ, ಅವುಗಳನ್ನು ನೆಸ್ಟೆಡ್ ಮಾಡಿದ ಕ್ರಮದಲ್ಲಿ, ವೆರಿಫೈಯರ್ ಅಸ್ತಿತ್ವದಲ್ಲಿರುವ ಕ್ವಾಂಟಿಫೈಡ್ ವೇರಿಯೇಬಲ್ಗಳನ್ನು ತುಂಬುತ್ತದೆ ಮತ್ತು ಫಾಲ್ಸಿಫೈಯರ್ ಸಾರ್ವತ್ರಿಕವಾಗಿ ಕ್ವಾಂಟಿಫೈಡ್ ವೇರಿಯೇಬಲ್ಗಳನ್ನು ತುಂಬುತ್ತದೆ; ಫಿಲ್ಡ್-ಇನ್ ಸೂತ್ರವು ನಿಜವಾದರೆ ವೆರಿಫೈಯರ್ ಗೆಲ್ಲುತ್ತಾನೆ, ಮತ್ತು ಇಲ್ಲದಿದ್ದರೆ ಫಾಲ್ಸಿಫೈಯರ್ ಗೆಲ್ಲುತ್ತಾನೆ. ಪರಿಶೀಲಿಸುವವರು ಗೆಲ್ಲುವ ಕಾರ್ಯತಂತ್ರವನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಪ್ರಮಾಣೀಕೃತ ಸೂತ್ರವು ನಿಜವಾಗಿದೆ. ಅಂತೆಯೇ, ಇತರ ಅನೇಕ ಸಂಯೋಜಿತ ಆಟಗಳ ವಿಜೇತ ಅಥವಾ ಸೋತವರನ್ನು ನಿರ್ಧರಿಸುವ ಸಮಸ್ಯೆಯು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣವಾಗಿದೆ. ಹೆಕ್ಸ್ ಮತ್ತು ರಿವರ್ಸಿ ಆಟಗಳು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಕಂಪ್ಲೀಟ್ ಆಟಗಳಿಗೆ ಉದಾಹರಣೆಗಳಾಗಿವೆ (ಸಾಮಾನ್ಯೀಕರಿಸಿದಾಗ ಅವುಗಳನ್ನು ಫಲಕದಲ್ಲಿ ಆಡಬಹುದು). ಚೆಸ್, ಚೆಕರ್ಸ್ (ಡ್ರಾಫ್ಟ್ಗಳು) ಮತ್ತು ಗೋ ಮುಂತಾದ ಇತರ ಕೆಲವು ಸಾಮಾನ್ಯ ಆಟಗಳು ಎಕ್ಸ್ಪೆಟಿಮ್-ಪೂರ್ಣವಾಗಿವೆ ಏಕೆಂದರೆ ಇಬ್ಬರು ಪರಿಪೂರ್ಣ ಆಟಗಾರರ ನಡುವಿನ ಆಟವು ತುಂಬಾ ಉದ್ದವಾಗಿರಬಹುದು, ಆದ್ದರಿಂದ ಅವು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ನಲ್ಲಿರುವ ಸಾಧ್ಯತೆಯಿಲ್ಲ. ಆದರೆ ಚಲನೆಗಳ ಸಂಖ್ಯೆಯ ಮೇಲೆ ಬಹುಪದವನ್ನು ನಿರ್ಬಂಧಿಸಿದರೆ ಅವು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣಗೊಳ್ಳುತ್ತವೆ. ಒಬ್ಬ ಆಟಗಾರ ಆಡುವ ಒಗಟುಗಳು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಕಂಪ್ಲೀಟ್ ಆಗಿರಲು ಸಹ ಸಾಧ್ಯವಿದೆ. ಇವುಗಳನ್ನು ಆಗಾಗ್ಗೆ ಪುನಾರಚನೆ ಸಮಸ್ಯೆಗಳು ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು ಮತ್ತು ಸಾಲಿಟೈರ್ ಆಟಗಳಾದ ರಶ್ ಅವರ್, ಮಹ್ಜಾಂಗ್, ಅಟಾಮಿಕ್ಸ್ ಮತ್ತು ಸೊಕೊಬನ್ ಮತ್ತು ಮೆಕ್ಯಾನಿಕಲ್ ಕಂಪ್ಯೂಟರ್ ಟ್ಯೂರಿಂಗ್ ಟಂಬಲ್ ಅನ್ನು ಒಳಗೊಂಡಿವೆ. ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಸಂಪೂರ್ಣತೆಯು ಇನ್ಪುಟ್ ಗಾತ್ರದ ಕಾರ್ಯವಾಗಿ ಸಂಕೀರ್ಣತೆಯನ್ನು ಆಧರಿಸಿದೆ, ಮಿತಿಯಲ್ಲಿ ಮಿತಿಯಿಲ್ಲದೆ ಬೆಳೆಯುತ್ತದೆ. ಸಾಂಪ್ರದಾಯಿಕ ಫಲಕದಲ್ಲಿ ಚೆಸ್ನಂತಹ ಸೀಮಿತ ಸಂಖ್ಯೆಯ ಸ್ಥಾನಗಳನ್ನು ಹೊಂದಿರುವ ಒಗಟುಗಳು ಅಥವಾ ಆಟಗಳು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣವಾಗಿರಲು ಸಾಧ್ಯವಿಲ್ಲ, ಏಕೆಂದರೆ ಅವುಗಳನ್ನು ಬಹಳ ದೊಡ್ಡ ಲುಕ್ಅಪ್ ಟೇಬಲ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಸ್ಥಿರ ಸಮಯ ಮತ್ತು ಜಾಗದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಈ ಆಟಗಳ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣ ಆವೃತ್ತಿಗಳನ್ನು ರೂಪಿಸಲು, ಅವುಗಳ ಸ್ಥಾನಗಳ ಸಂಖ್ಯೆಯನ್ನು ಮಿತಿಯಿಲ್ಲದ ರೀತಿಯಲ್ಲಿ ಮಾರ್ಪಡಿಸಬೇಕು, ಉದಾಹರಣೆಗೆ ಅವುಗಳನ್ನು ಫಲಕದ ಮೇಲೆ ಆಡುವುದು. ಚದುರಂಗದಂತಹ ಕೆಲವು ಸಂದರ್ಭಗಳಲ್ಲಿ, ಈ ವಿಸ್ತರಣೆಗಳು ಕೃತಕವಾಗಿರುತ್ತವೆ. ಹೆಚ್ಚಿನ ಓದುವ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗಗಳ ಉಲ್ಲೇಖಗಳು