Cobham's thesis
ಕೋಬ್ಹ್ಯಾಮ್-ಎಡ್ಮಂಡ್ಸ್ ಪ್ರಬಂಧ ಎಂದೂ ಕರೆಯಲ್ಪಡುವ ಕೋಬ್ಹ್ಯಾಮ್ನ ಪ್ರಬಂಧವು (ಅಲನ್ ಕೋಬ್ಹ್ಯಾಮ್ ಮತ್ತು ಜ್ಯಾಕ್ ಎಡ್ಮಂಡ್ಸ್ ಅವರ ಹೆಸರನ್ನು ಇಡಲಾಗಿದೆ), ಗಣನೆಯ ಸಮಸ್ಯೆಗಳನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದಾದರೆ ಮಾತ್ರ ಕೆಲವು ಗಣನೆಯ ಸಾಧನಗಳಲ್ಲಿ ಕಾರ್ಯಸಾಧ್ಯವಾಗಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು ಎಂದು ಪ್ರತಿಪಾದಿಸುತ್ತದೆ; ಅಂದರೆ, ಅವು ಸಂಕೀರ್ಣತೆಯ ವರ್ಗ ಪಿ. ಆಧುನಿಕ ಪರಿಭಾಷೆಯಲ್ಲಿ, ಇದು ಸಂಕೀರ್ಣತೆಯ ವರ್ಗ ಪಿ. ಯೊಂದಿಗೆ ಪರಿಹರಿಸಬಹುದಾದ ಸಮಸ್ಯೆಗಳನ್ನು ಗುರುತಿಸುತ್ತದೆ. ಔಪಚಾರಿಕವಾಗಿ, ಒಂದು ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು ಎಂದು ಹೇಳುವುದು, ಒಂದು ಅಲ್ಗಾರಿದಮ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ ಎಂದು ಹೇಳುವುದು, ಸಮಸ್ಯೆಯ ಎನ್-ಬಿಟ್ ಉದಾಹರಣೆಯನ್ನು ಇನ್ಪುಟ್ ಆಗಿ ನೀಡಿದರೆ, ದೊಡ್ಡ-ಓ ಸಂಕೇತವನ್ನು ಬಳಸಿಕೊಂಡು ಒ (ಎನ್ಸಿ) ಸಮಯದಲ್ಲಿ ಪರಿಹಾರವನ್ನು ಉತ್ಪಾದಿಸಬಹುದು ಮತ್ತು ಸಿ ಸಮಸ್ಯೆಯ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿರುವ ಸ್ಥಿರಾಂಕವಾಗಿರಬಹುದು ಆದರೆ ಸಮಸ್ಯೆಯ ಮೇಲೆ ಅಲ್ಲ. "ಕಾರ್ಯಗಳ ಆಂತರಿಕ ಕಂಪ್ಯೂಟೇಶನಲ್ ತೊಂದರೆ" ಎಂಬ ಶೀರ್ಷಿಕೆಯ ಅಲನ್ ಕೋಬ್ಹ್ಯಾಮ್ ಅವರ 1965 ರ ಪ್ರಬಂಧವು ಸಂಕೀರ್ಣತೆಯ ವರ್ಗ P ಯ ಪರಿಕಲ್ಪನೆಯ ಆರಂಭಿಕ ಉಲ್ಲೇಖಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ, ಇದು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ನಿರ್ಣಾಯಕ ಸಮಸ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಈ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗವು ಸಂಭಾವ್ಯವಾಗಿ ಗಣಿಸಬಹುದಾದ ಸಮಸ್ಯೆಗಳ ಗುಂಪನ್ನು ವಿವರಿಸಲು ಉತ್ತಮ ಮಾರ್ಗವಾಗಿದೆ ಎಂದು ಕೋಬ್ಹ್ಯಾಮ್ ಸಿದ್ಧಾಂತೀಕರಿಸಿದರು. ಜ್ಯಾಕ್ ಎಡ್ಮಂಡ್ಸ್ ಅವರ 1965 ರ ಪ್ರಬಂಧ "ಪಥಗಳು, ಮರಗಳು, ಮತ್ತು ಹೂವುಗಳು" ಸಹ P ಅನ್ನು ಪರಿಹರಿಸಬಹುದಾದ ಸಮಸ್ಯೆಗಳೊಂದಿಗೆ ಗುರುತಿಸಿದ ಕೀರ್ತಿಗೆ ಪಾತ್ರವಾಗಿದೆ. ಕೋಬಮ್ ಅವರ ಪ್ರಬಂಧವು ಗಣನೆಯ ಸಂಕೀರ್ಣತೆಯ ಸಿದ್ಧಾಂತದ ಅಭಿವೃದ್ಧಿಯಲ್ಲಿ ಒಂದು ಪ್ರಮುಖ ಮೈಲಿಗಲ್ಲಾಗಿದ್ದರೂ, ಇದು ಕ್ರಮಾವಳಿಗಳ ಪ್ರಾಯೋಗಿಕ ಕಾರ್ಯಸಾಧ್ಯತೆಗೆ ಅನ್ವಯವಾಗುವ ಮಿತಿಗಳನ್ನು ಹೊಂದಿದೆ. ಪ್ರಬಂಧವು ಮೂಲಭೂತವಾಗಿ "ಪಿ" ಎಂದರೆ "ಸುಲಭ, ವೇಗ ಮತ್ತು ಪ್ರಾಯೋಗಿಕ", ಆದರೆ "ಪಿ ನಲ್ಲಿ ಇಲ್ಲ" ಎಂದರೆ "ಕಠಿಣ, ನಿಧಾನ ಮತ್ತು ಅಪ್ರಾಯೋಗಿಕ" ಎಂದು ಹೇಳುತ್ತದೆ. ಆದರೆ ಇದು ಯಾವಾಗಲೂ ನಿಜವಲ್ಲ, ಏಕೆಂದರೆ ಪ್ರಬಂಧವು ಆಚರಣೆಯಲ್ಲಿ ರನ್ಟೈಮ್ನ ಮೇಲೆ ಪ್ರಭಾವ ಬೀರುವ ಕೆಲವು ಪ್ರಮುಖ ಅಸ್ಥಿರಗಳನ್ನು ಅಮೂರ್ತಗೊಳಿಸುತ್ತದೆಃ ಇದು ಸ್ಥಿರವಾದ ಅಂಶಗಳು ಮತ್ತು ಕೆಳ ಕ್ರಮಾಂಕದ ಪದಗಳನ್ನು ನಿರ್ಲಕ್ಷಿಸುತ್ತದೆ. ಇದು ಘಾತಾಂಕದ ಗಾತ್ರವನ್ನು ನಿರ್ಲಕ್ಷಿಸುತ್ತದೆ. ಸಮಯದ ಕ್ರಮಾನುಗತ ಪ್ರಮೇಯವು ಅನಿಯಂತ್ರಿತವಾಗಿ ದೊಡ್ಡ ಘಾತಾಂಕಗಳ ಅಗತ್ಯವಿರುವ Pಯಲ್ಲಿನ ಸಮಸ್ಯೆಗಳ ಅಸ್ತಿತ್ವವನ್ನು ಸಾಬೀತುಪಡಿಸುತ್ತದೆ. ಇದು ಇನ್ಪುಟ್ನ ವಿಶಿಷ್ಟ ಗಾತ್ರವನ್ನು ನಿರ್ಲಕ್ಷಿಸುತ್ತದೆ. ಈ ಮೂರೂ ಸಂಬಂಧಿತವಾಗಿವೆ ಮತ್ತು ಕ್ರಮಾವಳಿಗಳ ವಿಶ್ಲೇಷಣೆಯ ಬಗ್ಗೆ ಸಾಮಾನ್ಯ ದೂರುಗಳಾಗಿವೆ, ಆದರೆ ಅವು ವಿಶೇಷವಾಗಿ ಕೋಬಮ್ ಅವರ ಪ್ರಬಂಧಕ್ಕೆ ಅನ್ವಯಿಸುತ್ತವೆ, ಏಕೆಂದರೆ ಇದು ಪ್ರಾಯೋಗಿಕತೆಯ ಬಗ್ಗೆ ಸ್ಪಷ್ಟವಾದ ಹೇಳಿಕೆಯನ್ನು ನೀಡುತ್ತದೆ. ಕೋಬಮ್ ಅವರ ಪ್ರಬಂಧದ ಅಡಿಯಲ್ಲಿ, ಅತ್ಯುತ್ತಮ ಅಲ್ಗಾರಿದಮ್ n200 ಸೂಚನೆಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಸಮಸ್ಯೆಯನ್ನು ಕಾರ್ಯಸಾಧ್ಯವೆಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ ಮತ್ತು 20.00001 n ಸೂಚನೆಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಅಲ್ಗಾರಿದಮ್ನಲ್ಲಿನ ಸಮಸ್ಯೆಯನ್ನು ಕಾರ್ಯಸಾಧ್ಯವಲ್ಲವೆಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ-ಹಿಂದಿನ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ ಗಾತ್ರ n = 2 ರ ಉದಾಹರಣೆಯನ್ನು ಎಂದಿಗೂ ಪರಿಹರಿಸಲು ಸಾಧ್ಯವಾಗದಿದ್ದರೂ, ಗಾತ್ರ n = 106 ರ ನಂತರದ ಸಮಸ್ಯೆಯ ಉದಾಹರಣೆಯನ್ನು ಕಷ್ಟವಿಲ್ಲದೆ ಪರಿಹರಿಸಬಹುದು. ಪ್ರಾಯೋಗಿಕ ಸಮಸ್ಯೆಗಳು ಲಕ್ಷಾಂತರ ಅಸ್ಥಿರಗಳನ್ನು ಹೊಂದಿರುವ ಕ್ಷೇತ್ರಗಳಲ್ಲಿ (ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಶೋಧನೆ ಅಥವಾ ಎಲೆಕ್ಟ್ರಾನಿಕ್ ಡಿಸೈನ್ ಆಟೊಮೇಷನ್ನಂತಹ), O (n3) ಕ್ರಮಾವಳಿಗಳು ಸಹ ಸಾಮಾನ್ಯವಾಗಿ ಅಪ್ರಾಯೋಗಿಕವಾಗಿರುತ್ತವೆ. ಒಂದು ಪ್ರತ್ಯೇಕ ಪರಿಗಣನೆಯೆಂದರೆ, ಅನೇಕ ಸಂದರ್ಭಗಳಲ್ಲಿ, ನಿಖರವಾದ ಪರಿಹಾರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಾಗದಿದ್ದರೆ ಅಂದಾಜು ಪರಿಹಾರಗಳೊಂದಿಗೆ ಒಬ್ಬರು ಹೆಚ್ಚಾಗಿ ತೃಪ್ತರಾಗುತ್ತಾರೆ. ಉದಾಹರಣೆಗೆ, ಟ್ರಾವೆಲಿಂಗ್ ಸೇಲ್ಸ್ಮ್ಯಾನ್ ಸಮಸ್ಯೆಯು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ನಿಖರವಾಗಿ ಪರಿಹರಿಸಲಾಗುವುದಿಲ್ಲ ಎಂದು ವ್ಯಾಪಕವಾಗಿ ಶಂಕಿಸಲಾಗಿದೆ (ಇದು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಆಗಿದೆ), ಆದರೆ ಕ್ರಿಸ್ಟೋಫೈಡ್ಸ್ ಅಲ್ಗಾರಿದಮ್ನಂತಹ ವಿಧಾನಗಳೊಂದಿಗೆ ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಉತ್ತಮ ಪರಿಹಾರಗಳನ್ನು ಪಡೆಯಬಹುದು. ಉಲ್ಲೇಖಗಳು ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತ