P-complete
ಕಂಪ್ಯೂಟೇಶನಲ್ ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯು ಪಿ-ಕಂಪ್ಲೀಟ್ (ಸಂಕೀರ್ಣತೆ ವರ್ಗ ಪಿ ಗೆ ಪೂರ್ಣ) ಆಗಿದ್ದರೆ ಅದು ಪಿ ನಲ್ಲಿದೆ ಮತ್ತು ಪಿ ಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆಯನ್ನು ಸೂಕ್ತವಾದ ಕಡಿತದಿಂದ ಅದಕ್ಕೆ ಕಡಿಮೆ ಮಾಡಬಹುದು. ಪಿ-ಕಂಪ್ಲೀಟ್ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಳ ಕಲ್ಪನೆಯು ಈ ಕೆಳಗಿನವುಗಳ ವಿಶ್ಲೇಷಣೆಯಲ್ಲಿ ಉಪಯುಕ್ತವಾಗಿದೆಃ ಯಾವ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಸಮಾನಾಂತರಗೊಳಿಸುವುದು ಕಷ್ಟ, ಯಾವ ಸಮಸ್ಯೆಗಳನ್ನು ಸೀಮಿತ ಜಾಗದಲ್ಲಿ ಪರಿಹರಿಸುವುದು ಕಷ್ಟ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಪಾಲಿಟೈಮ್-ರಿಡ್ಯೂಸಿಬಿಲಿಟಿಗಿಂತ ರಿಡ್ಯೂಸಿಬಿಲಿಟಿಯ ಬಲವಾದ ಕಲ್ಪನೆಗಳನ್ನು ಪರಿಗಣಿಸಿದಾಗ. ಬಳಸಿದ ನಿರ್ದಿಷ್ಟ ರೀತಿಯ ಕಡಿತವು ಬದಲಾಗುತ್ತದೆ ಮತ್ತು ನಿಖರವಾದ ಸಮಸ್ಯೆಗಳ ಗುಂಪಿನ ಮೇಲೆ ಪರಿಣಾಮ ಬೀರಬಹುದು. ಸಾಮಾನ್ಯವಾಗಿ, ಬಹುಪದ-ಸಮಯದ ಕಡಿತಗಳಿಗಿಂತ ಬಲವಾದ ಕಡಿತಗಳನ್ನು ಬಳಸಲಾಗುತ್ತದೆ, ಏಕೆಂದರೆ ಬಹುಪದ-ಸಮಯದ ಕಡಿತಗಳ ಅಡಿಯಲ್ಲಿ ಪಿ ಯಲ್ಲಿನ ಎಲ್ಲಾ ಭಾಷೆಗಳು (ಖಾಲಿ ಭಾಷೆ ಮತ್ತು ಎಲ್ಲಾ ತಂತಿಗಳ ಭಾಷೆಯನ್ನು ಹೊರತುಪಡಿಸಿ) ಪಿ-ಪೂರ್ಣವಾಗಿವೆ. ನಾವು ಎನ್ಸಿ ಕಡಿತಗಳನ್ನು ಬಳಸಿದರೆ, ಅಂದರೆ ಬಹುಪದೀಯ ಸಂಖ್ಯೆಯ ಪ್ರೊಸೆಸರ್ಗಳೊಂದಿಗೆ ಸಮಾನಾಂತರ ಕಂಪ್ಯೂಟರ್ನಲ್ಲಿ ಬಹುಪದಗಣಿತೀಯ ಸಮಯದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸಬಹುದಾದ ಕಡಿತಗಳು, ನಂತರ ಎಲ್ಲಾ ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳು ಎನ್ಸಿಯ ಹೊರಗೆ ಇರುತ್ತವೆ ಮತ್ತು ಆದ್ದರಿಂದ ಎನ್ಸಿ § ಪಿ ಎಂದು ಸಾಬೀತುಪಡಿಸದ ಊಹೆಯ ಅಡಿಯಲ್ಲಿ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಸಮಾನಾಂತರಗೊಳಿಸಲಾಗುವುದಿಲ್ಲ. ಪ್ರೇರಣೆ ಪಿ ವರ್ಗವು ಸಾಮಾನ್ಯವಾಗಿ ಅನುಕ್ರಮ ಕಂಪ್ಯೂಟರ್ನ ಎಲ್ಲಾ "ಟ್ರ್ಯಾಕ್ ಮಾಡಬಹುದಾದ" ಸಮಸ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಇದು ವರ್ಗ ಎನ್. ಸಿ. ಯನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಇದು ಸಮಾನಾಂತರ ಕಂಪ್ಯೂಟರ್ನಲ್ಲಿ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಪರಿಹರಿಸಬಹುದಾದ ಸಮಸ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಏಕೆಂದರೆ ಸಮಾನಾಂತರ ಕಂಪ್ಯೂಟರ್ಗಳನ್ನು ಅನುಕ್ರಮ ಯಂತ್ರದಲ್ಲಿ ಅನುಕರಿಸಬಹುದು. NC = P ಎಂಬುದು ತಿಳಿದಿಲ್ಲ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಅಂತರ್ಗತವಾಗಿ ಅನುಕ್ರಮವಾಗಿರುವ ಯಾವುದೇ ಪರಿಹರಿಸಬಹುದಾದ ಸಮಸ್ಯೆಗಳಿವೆಯೇ ಎಂಬುದು ತಿಳಿದಿಲ್ಲ. P ಯು NP ಗೆ ಸಮನಾಗಿಲ್ಲ ಎಂದು ವ್ಯಾಪಕವಾಗಿ ಶಂಕಿಸಲಾಗಿರುವಂತೆಯೇ, NC ಯು P ಗೆ ಸಮನಾಗಿಲ್ಲ ಎಂದು ವ್ಯಾಪಕವಾಗಿ ಶಂಕಿಸಲಾಗಿದೆ. ಅಂತೆಯೇ, ವರ್ಗ L ಯು ಲಾಗರಿಥಮಿಕ್ ಜಾಗದಲ್ಲಿ ಅನುಕ್ರಮ ಕಂಪ್ಯೂಟರ್ನಿಂದ ಪರಿಹರಿಸಬಹುದಾದ ಎಲ್ಲಾ ಸಮಸ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಅಂತಹ ಯಂತ್ರಗಳು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತವೆ ಏಕೆಂದರೆ ಅವು ಬಹುಪದೀಯ ಸಂಖ್ಯೆಯ ಸಂರಚನೆಗಳನ್ನು ಹೊಂದಿರಬಹುದು. ಅಂದರೆ, ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದಾದ ಕೆಲವು ಸಮಸ್ಯೆಗಳಿಗೆ ಲಾಗರಿಥಮಿಕ್ ಸ್ಥಳಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಅಗತ್ಯವಿರುತ್ತದೆ ಎಂದು ಶಂಕಿಸಲಾಗಿದೆ. ಅದೇ ರೀತಿ ಪಿ = ಎನ್ಪಿ ಪ್ರಶ್ನೆಯನ್ನು ವಿಶ್ಲೇಷಿಸಲು ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಗಳ ಬಳಕೆಗೆ, ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಗಳು, "ಬಹುಶಃ ಸಮಾನಾಂತರವಾಗಿಲ್ಲ" ಅಥವಾ "ಬಹುಶಃ ಅಂತರ್ಗತವಾಗಿ ಅನುಕ್ರಮ" ಸಮಸ್ಯೆಗಳು ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ, ಇದು ಎನ್ಸಿ = ಪಿ ಪ್ರಶ್ನೆಯನ್ನು ಅಧ್ಯಯನ ಮಾಡಲು ಇದೇ ರೀತಿಯಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಕೆಲವು ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಗಳಿಗೆ ಪರಿಹಾರವನ್ನು ಸಮಾನಾಂತರಗೊಳಿಸಲು ಪರಿಣಾಮಕಾರಿ ಮಾರ್ಗವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಎನ್ಸಿ = ಪಿ ಎಂದು ತೋರಿಸುತ್ತದೆ. ಇದನ್ನು "ಸೂಪರ್ ಲಾಗರಿಥಮಿಕ್ ಸ್ಪೇಸ್ ಅಗತ್ಯವಿರುವ ಸಮಸ್ಯೆಗಳು" ಎಂದೂ ಪರಿಗಣಿಸಬಹುದು; ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಗೆ ಲಾಗ್-ಸ್ಪೇಸ್ ಪರಿಹಾರವು (ಲಾಗ್-ಸ್ಪೇಸ್ ಕಡಿತಗಳ ಆಧಾರದ ಮೇಲೆ ವ್ಯಾಖ್ಯಾನವನ್ನು ಬಳಸುವುದು) ಎಲ್ = ಪಿ ಅನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಇದರ ಹಿಂದಿನ ತರ್ಕವು ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಯ ಬಹುಪದ-ಸಮಯದ ಪರಿಹಾರವು ಪಿ = ಎನ್ಪಿ ಎಂದು ಸಾಬೀತುಪಡಿಸುತ್ತದೆ ಎಂಬ ತರ್ಕಕ್ಕೆ ಹೋಲುತ್ತದೆಃ ನಾವು ಪಿ ಯಲ್ಲಿನ ಯಾವುದೇ ಸಮಸ್ಯೆಯಿಂದ ಎ ಸಮಸ್ಯೆಗೆ ಎನ್ಸಿ ಕಡಿತವನ್ನು ಹೊಂದಿದ್ದರೆ, ಮತ್ತು ಎ ಗೆ ಎನ್ಸಿ ಪರಿಹಾರವನ್ನು ಹೊಂದಿದ್ದರೆ, ಎನ್ಸಿ = ಪಿ. ಅಂತೆಯೇ, ನಾವು ಪಿ ಯಲ್ಲಿನ ಯಾವುದೇ ಸಮಸ್ಯೆಯಿಂದ ಎ ಸಮಸ್ಯೆಗೆ ಲಾಗ್-ಸ್ಪೇಸ್ ಕಡಿತವನ್ನು ಹೊಂದಿದ್ದರೆ, ಮತ್ತು ಲಾಗ್-ಸ್ಪೇಸ್ ಅನ್ನು ಹೊಂದಿದ್ದರೆ. P ಯಲ್ಲಿನ ಯಾವುದೇ x ಗೆ, ಅದನ್ನು ಬಹುಪದ-ಸಮಯದಲ್ಲಿ ಸ್ವೀಕರಿಸುವ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದ ಎನ್ಕೋಡಿಂಗ್ ಅನ್ನು ಔಟ್ಪುಟ್ ಮಾಡಿ, x ನ ಎನ್ಕೋಡಿಂಗ್ ಮತ್ತು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದ ನಿರ್ಧಾರದ ಕಾರ್ಯಾಚರಣೆಯಲ್ಲಿ ಬಹುಪದ-ಸಮಯಕ್ಕೆ ಬದ್ಧವಾಗಿರುವ p ಗೆ ಅನುಗುಣವಾದ ಹಲವಾರು ಹಂತಗಳನ್ನು ಔಟ್ಪುಟ್ ಮಾಡಿ. x ಯು L ನಲ್ಲಿದ್ದರೆ ಮಾತ್ರ ಎಂ ಯಂತ್ರವು ಹಂತಗಳಲ್ಲಿ x ಮೇಲೆ ನಿಲ್ಲುತ್ತದೆ. ಸ್ಪಷ್ಟವಾಗಿ, ನಾವು ಅನುಕ್ರಮ ಕಂಪ್ಯೂಟರ್ನ ಸಾಮಾನ್ಯ ಅನುಕರಣೆಯನ್ನು ಸಮಾನಾಂತರಗೊಳಿಸಬಹುದಾದರೆ (ಅಂದರೆ. ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದ ಸಿಮ್ಯುಲೇಶನ್), ನಂತರ ನಾವು ಆ ಕಂಪ್ಯೂಟರ್ನಲ್ಲಿ ಚಲಿಸುವ ಯಾವುದೇ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ಸಮಾನಾಂತರಗೊಳಿಸಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ. ಈ ಸಮಸ್ಯೆಯು ಎನ್. ಸಿ. ಯಲ್ಲಿದ್ದರೆ, ಪಿ. ಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆಯೂ ಹಾಗೆಯೇ. ಹಂತಗಳ ಸಂಖ್ಯೆಯನ್ನು ದ್ವಿಮಾನದಲ್ಲಿ ಬರೆಯಲಾಗಿದ್ದರೆ, ಸಮಸ್ಯೆಯು ಎಕ್ಸ್ಟೈಮ್-ಕಂಪ್ಲೀಟ್ ಆಗಿರುತ್ತದೆ. ಈ ಸಮಸ್ಯೆಯು ಪಿ-ಸಂಪೂರ್ಣತೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಒಂದು ಸಾಮಾನ್ಯ ತಂತ್ರವನ್ನು ವಿವರಿಸುತ್ತದೆ. ಸಮಾನಾಂತರ ಯಂತ್ರದಲ್ಲಿ ಸಮಸ್ಯೆಯನ್ನು ತ್ವರಿತವಾಗಿ ಪರಿಹರಿಸಬಹುದೇ ಎಂಬುದರ ಬಗ್ಗೆ ನಮಗೆ ನಿಜವಾಗಿಯೂ ಆಸಕ್ತಿಯಿಲ್ಲ. ಅನುಕ್ರಮ ಯಂತ್ರಕ್ಕಿಂತ ಸಮಾನಾಂತರ ಯಂತ್ರವು ಅದನ್ನು ಹೆಚ್ಚು ವೇಗವಾಗಿ ಪರಿಹರಿಸುತ್ತದೆಯೇ ಎಂಬುದರ ಬಗ್ಗೆ ನಮಗೆ ಆಸಕ್ತಿ ಇದೆ. ಆದ್ದರಿಂದ, ನಾವು ಸಮಸ್ಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸಬೇಕಾಗಿರುವುದರಿಂದ ಅನುಕ್ರಮ ಆವೃತ್ತಿಯು ಪಿ. ಆಗಿರುತ್ತದೆ. ಅದಕ್ಕಾಗಿಯೇ ಈ ಸಮಸ್ಯೆಯು ಟಿ ಅನ್ನು ಯುನರಿ ಭಾಷೆಯಲ್ಲಿ ಬರೆಯಬೇಕಾಗಿತ್ತು. ಒಂದು ಸಂಖ್ಯೆ ಟಿ ಅನ್ನು ಬೈನರಿ ಸಂಖ್ಯೆಯಾಗಿ ಬರೆಯಲಾಗಿದ್ದರೆ (ಎನ್ ಒನ್ಸ್ ಮತ್ತು ಸೊನ್ನೆಗಳ ಸ್ಟ್ರಿಂಗ್, ಅಲ್ಲಿ ಎನ್ = ಲಾಗ್ ಟಿ), ಆಗ ಸ್ಪಷ್ಟ ಅನುಕ್ರಮ ಅಲ್ಗಾರಿದಮ್ 2n ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ಮತ್ತೊಂದೆಡೆ, ಟಿ ಅನ್ನು ಯೂನರಿ ಸಂಖ್ಯೆಯಾಗಿ ಬರೆಯಲಾಗಿದ್ದರೆ (n ಗಳ ಸ್ಟ್ರಿಂಗ್, ಅಲ್ಲಿ n = T), ಅದು ಕೇವಲ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಅದು ಅನುಕ್ರಮ ಸಮಸ್ಯೆಯನ್ನು ಪಿ ಯಲ್ಲಿ ಇರಿಸುತ್ತದೆ. ನಂತರ, ಅದು ಸಮಾನಾಂತರವಾಗಿದ್ದರೆ ಮಾತ್ರ ಅದು ಎನ್ಸಿಯಲ್ಲಿರುತ್ತದೆ. ಇತರ ಅನೇಕ ಸಮಸ್ಯೆಗಳು ಪಿ-ಕಂಪ್ಲೀಟ್ ಎಂದು ಸಾಬೀತಾಗಿವೆ ಮತ್ತು ಆದ್ದರಿಂದ ಅವುಗಳನ್ನು ಅಂತರ್ಗತವಾಗಿ ಅನುಕ್ರಮವೆಂದು ವ್ಯಾಪಕವಾಗಿ ನಂಬಲಾಗಿದೆ. ನೀಡಲಾಗಿರುವಂತೆ ಅಥವಾ ನಿರ್ಧಾರ-ಸಮಸ್ಯೆಯ ರೂಪದಲ್ಲಿ ಕನಿಷ್ಠ ಲಾಗ್ಸ್ಪೇಸ್ ಕಡಿತಗಳ ಅಡಿಯಲ್ಲಿ ಪಿ-ಪೂರ್ಣವಾಗಿರುವ ಈ ಕೆಳಗಿನ ಸಮಸ್ಯೆಗಳನ್ನು ಇವು ಒಳಗೊಂಡಿವೆಃ ಸರ್ಕ್ಯೂಟ್ ವ್ಯಾಲ್ಯೂ ಪ್ರಾಬ್ಲಮ್ (ಸಿ. ವಿ. ಪಿ)-ಸರ್ಕ್ಯೂಟ್, ಸರ್ಕ್ಯೂಟ್ಗೆ ಇನ್ಪುಟ್ಗಳು ಮತ್ತು ಸರ್ಕ್ಯೂಟ್ನಲ್ಲಿ ಒಂದು ಗೇಟ್ ಅನ್ನು ನೀಡಿದರೆ, ಆ ಗೇಟ್ನ ಔಟ್ಪುಟ್ ಅನ್ನು ಲೆಕ್ಕ ಹಾಕಿ. ಸಿ. ವಿ. ಪಿ. ಯ ನಿರ್ಬಂಧಿತ ಪ್ರಕರಣ-ಸಿ. ವಿ. ಪಿ. ಯಂತೆ, ಪ್ರತಿ ಗೇಟ್ ಎರಡು ಇನ್ಪುಟ್ಗಳು ಮತ್ತು ಎರಡು ಔಟ್ಪುಟ್ಗಳನ್ನು (ಎಫ್ ಮತ್ತು ನಾಟ್ ಎಫ್) ಹೊರತುಪಡಿಸಿ, ಪ್ರತಿಯೊಂದು ಪದರವು ಕೇವಲ ಎಂಡ್ ಗೇಟ್ಗಳು, ಉಳಿದವು ಒಆರ್ ಗೇಟ್ಗಳು (ಅಥವಾ, ಸಮಾನವಾಗಿ, ಎಲ್ಲಾ ಗೇಟ್ಗಳು ಎನ್ಎಎನ್ಡಿ ಗೇಟ್ಗಳು, ಅಥವಾ ಎಲ್ಲಾ ಗೇಟ್ಗಳು ಎನ್ಒಆರ್ ಗೇಟ್ಗಳು), ಗೇಟ್ನ ಇನ್ಪುಟ್ಗಳು ತಕ್ಷಣವೇ ಹಿಂದಿನ ಪದರದ ಲೀನಿಯರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ನಿಂದ ಬರುತ್ತವೆ-ರೇಖೀಯ ಅಸಮಾನತೆಯ ನಿರ್ಬಂಧಗಳಿಗೆ ಒಳಪಟ್ಟು ರೇಖೀಯ ಕಾರ್ಯವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಿ. ಸಂದರ್ಭ-ಮುಕ್ತ ವ್ಯಾಕರಣ ಸದಸ್ಯತ್ವ-ಸಂದರ್ಭ-ಮುಕ್ತ ವ್ಯಾಕರಣ ಮತ್ತು ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ನೀಡಿದರೆ, ಆ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಆ ವ್ಯಾಕರಣದಿಂದ ಉತ್ಪಾದಿಸಬಹುದೇ? ಹಾರ್ನ್-ತೃಪ್ತಿ-ಹಾರ್ನ್ ಷರತ್ತುಗಳ ಒಂದು ಗುಂಪನ್ನು ನೀಡಿದರೆ, ಅವುಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ವೇರಿಯೇಬಲ್ ನಿಯೋಜನೆ ಇದೆಯೇ? ಇದು ಬೂಲಿಯನ್ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಯ ಪಿ ಆವೃತ್ತಿಯಾಗಿದೆ. ಗೇಮ್ ಆಫ್ ಲೈಫ್-ಕಾನ್ವೇ ಅವರ ಗೇಮ್ ಆಫ್ ಲೈಫ್ನ ಆರಂಭಿಕ ಸಂರಚನೆಯನ್ನು ಗಮನಿಸಿದರೆ, ಒಂದು ನಿರ್ದಿಷ್ಟ ಕೋಶ ಮತ್ತು ಒಂದು ಸಮಯ ಟಿ (ಯುನಾರಿಯಲ್ಲಿ), ಟಿ ಹಂತಗಳ ನಂತರ ಆ ಕೋಶವು ಜೀವಂತವಾಗಿದೆಯೇ? LZW (ಅಲ್ಗಾರಿದಮ್) (1978 ಮಾದರಿ) ದತ್ತಾಂಶ ಸಂಕೋಚನ-ಕೊಟ್ಟಿರುವ ಸ್ಟ್ರಿಂಗ್ಗಳು s ಮತ್ತು t, LZ78 ವಿಧಾನದೊಂದಿಗೆ s ಅನ್ನು ಸಂಕುಚಿತಗೊಳಿಸುವುದರಿಂದ ನಿಘಂಟಿನಲ್ಲಿ t ಅನ್ನು ಸೇರಿಸುತ್ತದೆಯೇ? (gzip ನಂತಹ LZ77 ಸಂಕೋಚನಕ್ಕೆ, ಇದು ತುಂಬಾ ಸುಲಭ, ಏಕೆಂದರೆ ಸಮಸ್ಯೆಯು "Is t in s?" ಗೆ ಕಡಿಮೆಯಾಗುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ.) ಭಾಗಶಃ ಪ್ರಕಾರಗಳಿಗೆ ಊಹೆಯನ್ನು ಟೈಪ್ ಮಾಡಿ-ಲ್ಯಾಂಬ್ಡಾ ಕಲನಶಾಸ್ತ್ರದಿಂದ ಟೈಪ್ ಮಾಡದ ಪದವನ್ನು ನೀಡಿದರೆ, ಈ ಪದವು ಭಾಗಶಃ ಪ್ರಕಾರವನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸಿ. ಮೇಲಿನ ಹೆಚ್ಚಿನ ಭಾಷೆಗಳು ಏಕರೂಪದ ಅನೇಕ-ಒಂದು ಕಡಿತಗಳು, DLOGTIME ಕಡಿತಗಳು ಅಥವಾ ಪಾಲಿಲೋಗರಿಥಮಿಕ್ ಪ್ರಕ್ಷೇಪಗಳಂತಹ ಕಡಿತದ ಇನ್ನೂ ಬಲವಾದ ಕಲ್ಪನೆಗಳ ಅಡಿಯಲ್ಲಿ P-ಪೂರ್ಣವಾಗಿವೆ. ಪಿ ಯಲ್ಲಿ ನೀಡಲಾದ ಸಮಸ್ಯೆಯು ಪಿ-ಕಂಪ್ಲೀಟ್ ಎಂದು ಸಾಬೀತುಪಡಿಸಲು, ಒಬ್ಬರು ಸಾಮಾನ್ಯವಾಗಿ ತಿಳಿದಿರುವ ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಯನ್ನು ಕೊಟ್ಟಿರುವದಕ್ಕೆ ಕಡಿಮೆ ಮಾಡಲು ಪ್ರಯತ್ನಿಸುತ್ತಾರೆ. 1999ರಲ್ಲಿ, ಜಿನ್-ಯಿ ಕೈ ಮತ್ತು ಡಿ. ಶಿವಕುಮಾರ್ ಅವರು ಓಗಿಹಾರ ಅವರ ಕೃತಿಯ ಆಧಾರದ ಮೇಲೆ, ಪಿ-ಕಂಪ್ಲೀಟ್ ಎಂಬ ವಿರಳವಾದ ಭಾಷೆ ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ, ಎಲ್ = ಪಿ. ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಗಳನ್ನು ವಿಭಿನ್ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಗಳೊಂದಿಗೆ ಪರಿಹರಿಸಬಹುದು ಎಂದು ತೋರಿಸಿದರು. ಉದಾಹರಣೆಗೆ, ಸರ್ಕ್ಯೂಟ್ ಮೌಲ್ಯದ ಸಮಸ್ಯೆಯನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಟೋಪೋಲಾಜಿಕಲ್ ವಿಂಗಡಣೆಯಿಂದ ಪರಿಹರಿಸಬಹುದು. ಸಹಜವಾಗಿ, ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಯ ಕಡಿತಗಳು ವಿಭಿನ್ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಗಳನ್ನು ಹೊಂದಿರಬಹುದು, ಈ ಸಂಗತಿಯು ಪಿ ಯಲ್ಲಿನ ಎಲ್ಲಾ ಸಮಸ್ಯೆಗಳನ್ನು ಸಹ ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು ಎಂದು ಸೂಚಿಸುವುದಿಲ್ಲ. ಪಿ-ಕಂಪ್ಲೀಟ್ ಎಂದು ತಿಳಿದಿಲ್ಲದ ಸಮಸ್ಯೆಗಳು ಕೆಲವು ಎನ್ಪಿ-ಸಮಸ್ಯೆಗಳು ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಅಥವಾ ಪಿ ಎಂದು ತಿಳಿದಿಲ್ಲ. ಫ್ಯಾಕ್ಟರಿಂಗ್, ಗ್ರಾಫ್ ಐಸೊಮಾರ್ಫಿಸಮ್, ಪ್ಯಾರಿಟಿ ಆಟಗಳು) ಕಷ್ಟವೆಂದು ಶಂಕಿಸಲಾಗಿದೆ. ಅಂತೆಯೇ ಪಿ ಯಲ್ಲಿ ಪಿ-ಕಂಪ್ಲೀಟ್ ಅಥವಾ ಎನ್. ಸಿ ಎಂದು ತಿಳಿದಿಲ್ಲದ ಸಮಸ್ಯೆಗಳಿವೆ, ಆದರೆ ಸಮಾನಾಂತರಗೊಳಿಸಲು ಕಷ್ಟವೆಂದು ಭಾವಿಸಲಾಗಿದೆ. ಎರಡು ಸಂಖ್ಯೆಗಳ ಅತಿದೊಡ್ಡ ಸಾಮಾನ್ಯ ಭಾಜಕವನ್ನು ಕಂಡುಹಿಡಿಯುವ ನಿರ್ಧಾರ ಸಮಸ್ಯೆಯ ರೂಪಗಳು, ಎರಡು ಸಂಖ್ಯೆಗಳನ್ನು ನೀಡಿದಾಗ ವಿಸ್ತೃತ ಯೂಕ್ಲಿಡಿಯನ್ ಅಲ್ಗಾರಿದಮ್ ಯಾವ ಉತ್ತರವನ್ನು ನೀಡುತ್ತದೆ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವುದು ಮತ್ತು ದೊಡ್ಡ ಪೂರ್ಣಾಂಕದ ತೂಕದೊಂದಿಗೆ ಗ್ರಾಫ್ನ ಗರಿಷ್ಠ ತೂಕದ ಹೊಂದಾಣಿಕೆಯನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವುದು ಉದಾಹರಣೆಗಳಲ್ಲಿ ಸೇರಿವೆ. ಉಲ್ಲೇಖಗಳು ಗ್ರೀನ್ಲಾ, ರೇಮಂಡ್, ಜೇಮ್ಸ್ ಹೂವರ್ ಮತ್ತು ವಾಲ್ಟರ್ ರುಝೊ. 1995 ರಲ್ಲಿ. ಸಮಾನಾಂತರ ಗಣನೆಯ ಮಿತಿಗಳು; ಪಿ-ಸಂಪೂರ್ಣತೆ ಸಿದ್ಧಾಂತ. .. - ಸಿದ್ಧಾಂತವನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸುತ್ತದೆ, ನಂತರ 96 ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡುತ್ತದೆ. ಸಟೋರೋ ಮಿಯಾನೋ, ಶುಜಿ ಶಿರೈಶಿ ಮತ್ತು ತಕಾಯೋಶಿ ಶೌಡೈ. ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳ ಪಟ್ಟಿ. ಕ್ಯೂಶು ವಿಶ್ವವಿದ್ಯಾಲಯ, ಆರ್. ಐ. ಎಫ್. ಐ. ಎಸ್-ಟಿ. ಆರ್-ಸಿ. ಎಸ್-17. ಡಿಸೆಂಬರ್ 1990. ಸಂಕೀರ್ಣತೆ ತರಗತಿಗಳು