Berman–Hartmanis conjecture
ರಚನಾತ್ಮಕ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಬರ್ಮನ್-ಹಾರ್ಟ್ಮನಿಸ್ ಊಹೆಯು ಲಿಯೊನಾರ್ಡ್ ಸಿ. ಬರ್ಮನ್ ಮತ್ತು ಜ್ಯೂರಿಸ್ ಹಾರ್ಟ್ಮನಿಸ್ ಅವರ ಹೆಸರಿನಲ್ಲಿ ಹೆಸರಿಸಲಾದ ಒಂದು ಬಗೆಹರಿಯದ ಊಹೆಯಾಗಿದೆ, ಇದು ಎಲ್ಲಾ ಎನ್ಪಿ-ಪೂರ್ಣ ಭಾಷೆಗಳು ಒಂದೇ ರೀತಿ ಕಾಣುತ್ತವೆ ಎಂದು ಹೇಳುತ್ತದೆ, ಅಂದರೆ ಅವು ಬಹುಪದೀಯ ಸಮಯದ ಐಸೊಮಾರ್ಫಿಸಮ್ಗಳಿಂದ ಪರಸ್ಪರ ಸಂಬಂಧ ಹೊಂದಬಹುದು. ಔಪಚಾರಿಕ ಭಾಷೆಗಳಾದ L1 ಮತ್ತು L2 ನಡುವಿನ ಐಸೊಮಾರ್ಫಿಸಮ್ ಎಂಬುದು L1 ವರ್ಣಮಾಲೆಯಲ್ಲಿನ ತಂತಿಗಳಿಂದ L2 ವರ್ಣಮಾಲೆಯಲ್ಲಿನ ತಂತಿಗಳವರೆಗಿನ ಒಂದು ಬೈಜೆಕ್ಟಿವ್ ಮ್ಯಾಪ್ ಆಗಿದೆ, f (x) L2 ಗೆ ಸೇರಿದ್ದರೆ ಮತ್ತು ಮಾತ್ರ ಸ್ಟ್ರಿಂಗ್ x L1 ಗೆ ಸೇರಿದೆ ಎಂಬ ಗುಣಲಕ್ಷಣವನ್ನು ಹೊಂದಿದೆ. ಎಫ್ ಮತ್ತು ಅದರ ವಿಲೋಮ ಕಾರ್ಯ ಎರಡನ್ನೂ ಅವುಗಳ ವಾದಗಳ ಉದ್ದದಲ್ಲಿ ಸಮಯದ ಬಹುಪದದಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದಾದರೆ ಅದು ಬಹುಪದ ಸಮಯದ ಐಸೊಮಾರ್ಫಿಸಮ್ (ಅಥವಾ ಸಂಕ್ಷಿಪ್ತವಾಗಿ ಪಿ-ಐಸೊಮಾರ್ಫಿಸಮ್) ಆಗಿದೆ. ಆ ಸಮಯದಲ್ಲಿ ಎನ್. ಪಿ-ಕಂಪ್ಲೀಟ್ ಎಂದು ತಿಳಿದಿರುವ ಎಲ್ಲಾ ಭಾಷೆಗಳು ಪಿ-ಐಸೊಮಾರ್ಫಿಕ್ ಎಂದು ಗಮನಿಸಲಾಗಿದೆ. ಹೆಚ್ಚು ಬಲವಾಗಿ, ಆಗಿನ ಎಲ್ಲಾ ಪ್ರಸಿದ್ಧ ಎನ್. ಪಿ.-ಪೂರ್ಣ ಭಾಷೆಗಳು ಪ್ಯಾಡಬಲ್ ಎಂದು ಅವರು ಗಮನಿಸಿದರು, ಮತ್ತು ಪ್ಯಾಡಬಲ್ ಎನ್. ಪಿ.-ಪೂರ್ಣ ಭಾಷೆಗಳ ಎಲ್ಲಾ ಜೋಡಿಗಳು ಪಿ-ಐಸೊಮಾರ್ಫಿಕ್ ಎಂದು ಅವರು ಸಾಬೀತುಪಡಿಸಿದರು (ಮೈಹಿಲ್ ಐಸೊಮಾರ್ಫಿಸಮ್ ಪ್ರಮೇಯಕ್ಕೆ ಹೋಲುತ್ತದೆ). ಬಹುಪದ ಸಮಯ ವಿಲೋಮದೊಂದಿಗೆ ಬಹುಪದ ಸಮಯ ಕಾರ್ಯ f (x, y) ಇದ್ದರೆ ಮತ್ತು ಎಲ್ಲಾ x ಮತ್ತು y ಗೆ, x L ಗೆ ಸೇರಿದ್ದರೆ ಮತ್ತು f (x, y) L ಗೆ ಸೇರಿದ್ದರೆ ಮಾತ್ರ ಗುಣಲಕ್ಷಣದೊಂದಿಗೆ ಒಂದು ಭಾಷೆ L ಅನ್ನು ಪ್ಯಾಡ್ ಮಾಡಬಹುದುಃ ಅಂದರೆ, ಇನ್ಪುಟ್ x ಅನ್ನು ಅಪ್ರಸ್ತುತ ಮಾಹಿತಿಯೊಂದಿಗೆ y ಅನ್ನು ಇನ್ವರ್ಟಿಬಲ್ ರೀತಿಯಲ್ಲಿ, ಭಾಷೆಯಲ್ಲಿ ಅದರ ಸದಸ್ಯತ್ವವನ್ನು ಬದಲಾಯಿಸದೆ ಪ್ಯಾಡ್ ಮಾಡಲು ಸಾಧ್ಯವಿದೆ. ಈ ಫಲಿತಾಂಶಗಳ ಆಧಾರದ ಮೇಲೆ, ಎಲ್ಲಾ ಎನ್. ಪಿ.-ಪೂರ್ಣ ಭಾಷೆಗಳು ಪಿ-ಐಸೋಮಾರ್ಫಿಕ್ ಎಂದು ಬರ್ಮನ್ ಮತ್ತು ಹಾರ್ಟ್ಮನಿಸ್ ಊಹಿಸಿದ್ದಾರೆ. ಪಿ-ಐಸೋಮಾರ್ಫಿಸಮ್ ಪ್ಯಾಡಬಿಲಿಟಿಯನ್ನು ಸಂರಕ್ಷಿಸುತ್ತದೆಯಾದ್ದರಿಂದ, ಮತ್ತು ಪ್ಯಾಡಬಲ್ ಎನ್ಪಿ-ಸಂಪೂರ್ಣ ಭಾಷೆಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿರುವುದರಿಂದ, ಬರ್ಮನ್-ಹಾರ್ಟ್ಮನಿಸ್ ಊಹೆಯನ್ನು ಹೇಳುವ ಸಮಾನವಾದ ವಿಧಾನವೆಂದರೆ ಎಲ್ಲಾ ಎನ್ಪಿ-ಪೂರ್ಣ ಭಾಷೆಗಳು ಪ್ಯಾಡಬಲ್ ಆಗಿವೆ. ಬಹುಪದೀಯ ಸಮಯದ ಐಸೊಮಾರ್ಫಿಸಮ್ ಒಂದು ಸಮಾನತೆಯ ಸಂಬಂಧವಾಗಿದೆ, ಮತ್ತು ಇದನ್ನು ಔಪಚಾರಿಕ ಭಾಷೆಗಳನ್ನು ಸಮಾನತೆಯ ವರ್ಗಗಳಾಗಿ ವಿಭಜಿಸಲು ಬಳಸಬಹುದು, ಆದ್ದರಿಂದ ಬರ್ಮನ್-ಹಾರ್ಟ್ಮನಿಸ್ ಊಹೆಯನ್ನು ಹೇಳುವ ಮತ್ತೊಂದು ವಿಧಾನವೆಂದರೆ ಎನ್ಪಿ-ಪೂರ್ಣ ಭಾಷೆಗಳು ಈ ಸಂಬಂಧಕ್ಕೆ ಒಂದೇ ಸಮಾನತೆಯ ವರ್ಗವನ್ನು ರೂಪಿಸುತ್ತವೆ. ಪರಿಣಾಮಗಳು ಬರ್ಮನ್-ಹಾರ್ಟ್ಮನ್ನಿಸ್ ಊಹೆಯು ನಿಜವಾಗಿದ್ದರೆ, ವಿರಳವಾದ ಎನ್. ಪಿ.-ಪೂರ್ಣ ಭಾಷೆಗಳ ಅಸ್ತಿತ್ವವು ತಕ್ಷಣದ ಪರಿಣಾಮವಾಗಿರುತ್ತದೆ, ಅವುಗಳೆಂದರೆ n ನ ಕಾರ್ಯವಾಗಿ ಬಹುಪದಿಯಲ್ಲಿ ಮಾತ್ರ ಬೆಳೆಯುವ ಭಾಷೆಗಳು. ತಿಳಿದಿರುವ ಎನ್. ಪಿ.-ಪೂರ್ಣ ಭಾಷೆಗಳು ಘಾತೀಯವಾಗಿ ಬೆಳೆಯುವ ಹಲವಾರು ಹೌದು-ನಿದರ್ಶನಗಳನ್ನು ಹೊಂದಿವೆ, ಮತ್ತು ಎಲ್ ಘಾತೀಯವಾಗಿ ಅನೇಕ ಹೌದು-ನಿದರ್ಶನಗಳನ್ನು ಹೊಂದಿರುವ ಭಾಷೆಯಾಗಿದ್ದರೆ ಅದು ವಿರಳವಾದ ಭಾಷೆಗೆ ಪಿ-ಐಸೊಮಾರ್ಫಿಕ್ ಆಗಿರಲು ಸಾಧ್ಯವಿಲ್ಲ, ಏಕೆಂದರೆ ಅದರ ಹೌದು-ನಿದರ್ಶನಗಳನ್ನು ನಕ್ಷೆಯು ಒಂದರಿಂದ ಒಂದಾಗಿರಲು ಬಹುಪದಶಃ ಉದ್ದಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ತಂತಿಗಳಿಗೆ ಮ್ಯಾಪ್ ಮಾಡಬೇಕಾಗುತ್ತದೆ. ವಿರಳವಾದ ಎನ್. ಪಿ.-ಪೂರ್ಣ ಭಾಷೆಗಳ ಅಸ್ತಿತ್ವವು ಪ್ರತಿಯಾಗಿ ಪಿ ಷ್ಣ ಎನ್. ಪಿ. ಎಂದು ಸೂಚಿಸುತ್ತದೆ, ಏಕೆಂದರೆ ಪಿ = ಎನ್. ಪಿ. ಆಗಿದ್ದರೆ, ಪಿ ಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಕ್ಷುಲ್ಲಕವಲ್ಲದ ಭಾಷೆಯು (ಕೆಲವು ವಿರಳವಾದವುಗಳನ್ನು ಒಳಗೊಂಡಂತೆ, ಬೈನರಿ ತಂತಿಗಳ ಭಾಷೆಯು ಅದರ ಎಲ್ಲಾ ಬಿಟ್ಗಳು ಶೂನ್ಯವಾಗಿರುತ್ತವೆ) ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿರುತ್ತದೆ. 1982ರಲ್ಲಿ, ಸ್ಟೀವ್ ಮಹಾನೆಯವರು, ವಿರಳವಾದ ಎನ್. ಪಿ.-ಸಂಪೂರ್ಣ ಭಾಷೆಗಳ ಅಸ್ತಿತ್ವವಿಲ್ಲದಿರುವುದು (ಅನೇಕ-ಒಂದು ಕಡಿತಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಪ್ರಮಾಣಿತ ರೀತಿಯಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಎನ್. ಪಿ.-ಸಂಪೂರ್ಣತೆಯೊಂದಿಗೆ) ವಾಸ್ತವವಾಗಿ ಪಿ ≤ ಎನ್. ಪಿ. ಎಂಬ ಹೇಳಿಕೆಗೆ ಸಮಾನವಾಗಿದೆ ಎಂದು ತಮ್ಮ ಪುರಾವೆಯನ್ನು ಪ್ರಕಟಿಸಿದರು; ಇದು ಮಹಾನೆಯ ಪ್ರಮೇಯವಾಗಿದೆ. ಟ್ಯೂರಿಂಗ್ ಕಡಿತಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಎನ್. ಪಿ.-ಸಂಪೂರ್ಣತೆಯ ಸಡಿಲವಾದ ವ್ಯಾಖ್ಯಾನಕ್ಕೂ ಸಹ, ವಿರಳವಾದ ಎನ್. ಪಿ.-ಪೂರ್ಣ ಭಾಷೆಯ ಅಸ್ತಿತ್ವವು ಬಹುಪದ ಶ್ರೇಣಿವ್ಯವಸ್ಥೆಯ ಅನಿರೀಕ್ಷಿತ ಕುಸಿತವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಊಹೆಯ ಬಗೆಗಿನ ಪುರಾವೆಯಾಗಿ, ನಿರ್ಬಂಧಿತ ರೀತಿಯ ಕಡಿತದೊಂದಿಗೆ ಸದೃಶವಾದ ಊಹೆಯು ನಿಜವೆಂದು ತೋರಿಸಿದೆಃ ಎಸಿ0 ಅನೇಕ-ಒಂದು ಕಡಿತಗಳ ಅಡಿಯಲ್ಲಿ ಎನ್ಪಿಗೆ ಪೂರ್ಣವಾಗಿರುವ ಪ್ರತಿ ಎರಡು ಭಾಷೆಗಳು ಎಸಿ0 ಐಸೊಮಾರ್ಫಿಸಮ್ ಅನ್ನು ಹೊಂದಿವೆ. ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳ ಮೇಲೆ ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ತಲೆಕೆಳಗಾಗಿಸಲಾಗದ ಏಕಮುಖ ಕಾರ್ಯಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ, ಆದರೆ ಅಂತಹ ಪ್ರತಿಯೊಂದು ಕಾರ್ಯವು ಪಿ/ಪಾಲಿಯಲ್ಲಿ ತಲೆಕೆಳಗಾಗಬಹುದಾದ ಸಣ್ಣ ಆದರೆ ದಟ್ಟವಾದ ಇನ್ಪುಟ್ಗಳ ಉಪವಿಭಾಗವನ್ನು ಹೊಂದಿದ್ದರೆ (ಈ ರೀತಿಯ ತಿಳಿದಿರುವ ಕಾರ್ಯಗಳಿಗೆ ನಿಜವಾಗಿದೆ) ಆಗ ಪ್ರತಿ ಎರಡು ಎನ್ಪಿ-ಪೂರ್ಣ ಭಾಷೆಗಳು ಪಿ/ಪಾಲಿ ಐಸೊಮಾರ್ಫಿಸಮ್ ಅನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಮತ್ತು ಒರಾಕಲ್ ಯಂತ್ರ ಮಾದರಿಯನ್ನು ಕಂಡುಕೊಂಡರು, ಇದರಲ್ಲಿ ಐಸೊಮಾರ್ಫಿಸಮ್ ಊಹೆಗೆ ಸಾದೃಶ್ಯವು ನಿಜವಾಗಿದೆ. ಊಹೆಯ ವಿರುದ್ಧ ಸಾಕ್ಷ್ಯವನ್ನು ಮತ್ತು ಒದಗಿಸಿದ್ದಾರೆ. ಜೋಸೆಫ್ ಮತ್ತು ಯಂಗ್ ಎನ್ಪಿ-ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆಗಳ ಒಂದು ವರ್ಗವನ್ನು ಪರಿಚಯಿಸಿದರು, ಕೆ-ಕ್ರಿಯಾತ್ಮಕ ಸೆಟ್ಗಳು, ಇದಕ್ಕಾಗಿ ಪ್ರಮಾಣಿತ ಎನ್ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳಿಗೆ ಯಾವುದೇ ಪಿ-ಐಸೊಮಾರ್ಫಿಸಮ್ ತಿಳಿದಿಲ್ಲ. ಕರ್ಟ್ಜ್ ಮತ್ತು ಇತರರು. ಯಾದೃಚ್ಛಿಕ ಒರಾಕಲ್ಗೆ ಪ್ರವೇಶವನ್ನು ನೀಡಲಾದ ಒರಾಕಲ್ ಯಂತ್ರ ಮಾದರಿಗಳಲ್ಲಿ, ಊಹೆಯ ಸಾದೃಶ್ಯವು ನಿಜವಲ್ಲ ಎಂದು ತೋರಿಸಿದೆಃ ಎ ಯಾದೃಚ್ಛಿಕ ಒರಾಕಲ್ ಆಗಿದ್ದರೆ, ಎನ್ಪಿಎಗೆ ಪೂರ್ಣಗೊಂಡ ಎಲ್ಲಾ ಸೆಟ್ಗಳು ಪಿಎನಲ್ಲಿ ಐಸೊಮಾರ್ಫಿಸಮ್ಗಳನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. ಯಾದೃಚ್ಛಿಕ ಒರಾಕಲ್ಗಳನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಕ್ರಿಪ್ಟೋಗ್ರಫಿಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಯಾದೃಚ್ಛಿಕದಿಂದ ಗಣನೆಗೆ ಪ್ರತ್ಯೇಕಿಸಲಾಗದ ಕ್ರಿಪ್ಟೋಗ್ರಾಫಿಕ್ ಹ್ಯಾಶ್ ಕಾರ್ಯಗಳನ್ನು ರೂಪಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ, ಮತ್ತು ಕರ್ಟ್ಜ್ ಮತ್ತು ಇತರರ ನಿರ್ಮಾಣ. ಒರಾಕಲ್ನ ಸ್ಥಳದಲ್ಲಿ ಅಂತಹ ಕಾರ್ಯವನ್ನು ನಿರ್ವಹಿಸಬಹುದು. ಈ ಕಾರಣಕ್ಕಾಗಿ, ಇತರರಲ್ಲಿ, ಬರ್ಮನ್-ಹಾರ್ಟ್ಮನಿಸ್ ಐಸೊಮಾರ್ಫಿಸಮ್ ಊಹೆಯನ್ನು ಅನೇಕ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತಿಗಳು ಸುಳ್ಳು ಎಂದು ನಂಬುತ್ತಾರೆ. ಸಂರಚನಾತ್ಮಕ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತ ಗಣಕ ವಿಜ್ಞಾನದಲ್ಲಿ ಪರಿಹರಿಸಲಾಗದ ಸಮಸ್ಯೆಗಳನ್ನು ಊಹಿಸುತ್ತದೆ ಗಣಿತದಲ್ಲಿ ಪರಿಹರಿಸಲಾಗದ ಸಮಸ್ಯೆಗಳು