Valiant–Vazirani theorem
ವ್ಯಾಲಿಯಂಟ್-ವಜೀರಾನಿ ಪ್ರಮೇಯವು ಗಣನೆಯ ಸಂಕೀರ್ಣತೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಒಂದು ಪ್ರಮೇಯವಾಗಿದ್ದು, ನಿಸ್ಸಂದಿಗ್ಧ-ಎಸ್ಎಟಿಗೆ ಬಹುಪದ ಸಮಯದ ಕ್ರಮಾವಳಿ ಇದ್ದರೆ, ಎನ್ಪಿ = ಆರ್ಪಿ ಎಂದು ಹೇಳುತ್ತದೆ. ಇದನ್ನು ಲೆಸ್ಲಿ ವಾಲಿಯಂಟ್ ಮತ್ತು ವಿಜಯ್ ವಜೀರಾನಿ ಅವರು 1986ರಲ್ಲಿ ಪ್ರಕಟವಾದ ಎನ್. ಪಿ. ಎಂಬ ಶೀರ್ಷಿಕೆಯ ತಮ್ಮ ಪ್ರಬಂಧದಲ್ಲಿ, ಅನನ್ಯ ಪರಿಹಾರಗಳನ್ನು ಪತ್ತೆಹಚ್ಚುವಷ್ಟು ಸುಲಭ ಎಂದು ಸಾಬೀತುಪಡಿಸಿದ್ದಾರೆ. ಪುರಾವೆಯು ಮುಲ್ಮುಲೆ-ವಜೀರಾನಿ-ವಜೀರಾನಿ ಪ್ರತ್ಯೇಕ ಲೆಮ್ಮಾವನ್ನು ಆಧರಿಸಿದೆ, ಇದನ್ನು ತರುವಾಯ ಸೈದ್ಧಾಂತಿಕ ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ ಹಲವಾರು ಪ್ರಮುಖ ಅನ್ವಯಿಕೆಗಳಿಗೆ ಬಳಸಲಾಯಿತು. ವಾಲಿಯಂಟ್-ವಜೀರಾನಿ ಪ್ರಮೇಯವು ಸೂಚಿಸುವ ಪ್ರಕಾರ, ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿರುವ ಬೂಲಿಯನ್ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಯು, ಇನ್ಪುಟ್ ನಿದರ್ಶನಗಳು ಗರಿಷ್ಠ ಒಂದು ತೃಪ್ತಿಕರ ನಿಯೋಜನೆಯನ್ನು ಹೊಂದುವ ಭರವಸೆ ನೀಡಿದ್ದರೂ ಸಹ, ಗಣನೆಯ ದೃಷ್ಟಿಯಿಂದ ಕಠಿಣ ಸಮಸ್ಯೆಯಾಗಿ ಉಳಿದಿದೆ. ಪ್ರೂಫ್ ಔಟ್ಲೈನ್ ಅನ್ಮ್ಬಿಗ್ಯುಯಸ್-ಎಸ್. ಎ. ಟಿ. ಯು, ಗರಿಷ್ಠ ಒಂದು ತೃಪ್ತಿಕರವಾದ ನಿಯೋಜನೆಯನ್ನು ಹೊಂದಿರುವ ಬೂಲಿಯನ್ ಸೂತ್ರವು ಅತೃಪ್ತಿಕರವಾಗಿದೆಯೇ ಅಥವಾ ನಿಖರವಾಗಿ ಒಂದು ತೃಪ್ತಿಕರವಾದ ನಿಯೋಜನೆಯನ್ನು ಹೊಂದಿದೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವ ಭರವಸೆಯ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಮೊದಲನೆಯದಾಗಿ, ನಿಸ್ಸಂದಿಗ್ಧ-ಸ್ಯಾಟಿನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ತಿರಸ್ಕರಿಸಬೇಕು ಮತ್ತು ಎರಡನೆಯದರಲ್ಲಿ ಅದು ಸೂತ್ರವನ್ನು ಸ್ವೀಕರಿಸಬೇಕು. ಸೂತ್ರವು ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚು ತೃಪ್ತಿಕರ ನಿಯೋಜನೆಯನ್ನು ಹೊಂದಿದ್ದರೆ, ಅಲ್ಗಾರಿದಮ್ನ ನಡವಳಿಕೆಯ ಮೇಲೆ ಯಾವುದೇ ಷರತ್ತು ಇರುವುದಿಲ್ಲ. ಪ್ರಾಮಿಸ್ ಪ್ರಾಬ್ಲೆಮ್ ಅನ್ಮ್ಬೀಗ್ಯುಯಸ್-ಸ್ಯಾಟ್ ಅನ್ನು ನಿರ್ಣಾಯಕವಲ್ಲದ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ನಿರ್ಧರಿಸಬಹುದು, ಅದು ಗರಿಷ್ಠ ಒಂದು ಸ್ವೀಕರಿಸುವ ಗಣನೆಯ ಮಾರ್ಗವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಈ ಅರ್ಥದಲ್ಲಿ, ಈ ಭರವಸೆಯ ಸಮಸ್ಯೆಯು ಯು. ಪಿ. ಸಂಕೀರ್ಣತೆಯ ವರ್ಗಕ್ಕೆ ಸೇರಿದೆ (ಇದನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಭಾಷೆಗಳಿಗೆ ಮಾತ್ರ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗುತ್ತದೆ). ವಾಲಿಯಂಟ್-ವಜೀರಾನಿ ಪ್ರಮೇಯದ ಪುರಾವೆಯು ಎಸ್. ಎ. ಟಿ ಯಿಂದ ಎಸ್. ಎ. ಟಿ. ಗೆ ಸಂಭವನೀಯ ಕಡಿತವನ್ನು ಒಳಗೊಂಡಿದೆ, ಅಂದರೆ, ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ, ಔಟ್ಪುಟ್ ಸೂತ್ರವು ಗರಿಷ್ಠ ಒಂದು ತೃಪ್ತಿಕರ ನಿಯೋಜನೆಯನ್ನು ಹೊಂದಿದೆ, ಮತ್ತು ಹೀಗಾಗಿ ನಿಸ್ಸಂದಿಗ್ಧ-ಎಸ್. ಎ. ಟಿ ಸಮಸ್ಯೆಯ ಭರವಸೆಯನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ. ಹೆಚ್ಚು ನಿಖರವಾಗಿ, ಕಡಿತವು ಯಾದೃಚ್ಛಿಕ ಬಹುಪದ-ಸಮಯದ ಕ್ರಮಾವಳಿಯಾಗಿದ್ದು, ಇದು ಬೂಲಿಯನ್ ಸೂತ್ರಕ್ಕೆ ಅಸ್ಥಿರಗಳೊಂದಿಗೆ ಬೂಲಿಯನ್ ಸೂತ್ರವನ್ನು ನಕ್ಷೆ ಮಾಡುತ್ತದೆ, ಅಂದರೆ ಪ್ರತಿಯೊಂದು ತೃಪ್ತಿಕರ ನಿಯೋಜನೆಯೂ ಸಹ ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ, ಮತ್ತು ತೃಪ್ತಿಕರವಾಗಿದ್ದರೆ, ಕನಿಷ್ಠ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ, ಒಂದು ಅನನ್ಯ ತೃಪ್ತಿಕರ ನಿಯೋಜನೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಕಡಿತವನ್ನು ಬಹುಪದೀಯ ಸಂಖ್ಯೆಯ ಬಾರಿ ಚಲಾಯಿಸುವ ಮೂಲಕ, ಪ್ರತಿ ಬಾರಿಯೂ ತಾಜಾ ಸ್ವತಂತ್ರ ಯಾದೃಚ್ಛಿಕ ಬಿಟ್ಗಳೊಂದಿಗೆ, ನಾವು ಸೂತ್ರಗಳನ್ನು ಪಡೆಯುತ್ತೇವೆ. ಆಯ್ಕೆ ಮಾಡುವಾಗ, ಕನಿಷ್ಠ ಒಂದು ಸೂತ್ರವು ತೃಪ್ತಿಕರವಾಗಿದ್ದರೆ, ಅದು ಅನನ್ಯವಾಗಿ ತೃಪ್ತಿಕರವಾಗಿರುವ ಸಂಭವನೀಯತೆಯನ್ನು ನಾವು ಪಡೆಯುತ್ತೇವೆ. ಇದು ಟ್ಯೂರಿಂಗ್ ಅನ್ನು ಎಸ್. ಎ. ಟಿ ಯಿಂದ ನಿಸ್ಸಂದಿಗ್ಧ-ಎಸ್. ಎ. ಟಿ. ಗೆ ಕಡಿತಗೊಳಿಸುತ್ತದೆ ಏಕೆಂದರೆ ಅಸಂದಿಗ್ಧ-ಎಸ್. ಎ. ಟಿ. ಗೆ ಊಹಿಸಲಾದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಅದರ ಮೇಲೆ ಆಹ್ವಾನಿಸಬಹುದು. ನಂತರ ತೃಪ್ತಿಕರವಾದ ನಿಯೋಜನೆಯು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ ಅದನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಎಸ್. ಎ. ಟಿ. ಯ ಸ್ವಯಂ-ಕಡಿತವನ್ನು ಬಳಸಬಹುದು. ಒಟ್ಟಾರೆಯಾಗಿ, ಎನ್ಪಿ = ಆರ್ಪಿ ಅನ್ನು ನಿಸ್ಸಂದಿಗ್ಧವಾಗಿದ್ದರೆ-ಎಸ್ಎಟಿಯನ್ನು ಆರ್ಪಿಯಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು ಎಂದು ಇದು ಸಾಬೀತುಪಡಿಸುತ್ತದೆ. ಸೂತ್ರದ ದ್ರಾವಣ ಸ್ಥಳವನ್ನು ಯಾದೃಚ್ಛಿಕ ಅಫೈನ್ ಹೈಪರ್ ಪ್ಲೇನ್ಗಳೊಂದಿಗೆ ಛೇದಿಸುವುದು ಕಡಿತದ ಉದ್ದೇಶವಾಗಿದೆ, ಅಲ್ಲಿ ಯಾದೃಚ್ಛಿಕವಾಗಿ ಏಕರೂಪವಾಗಿ ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ. ಪರ್ಯಾಯ ಪುರಾವೆಯು ಮುಲ್ಮುಲೆ, ವಜೀರಾನಿ ಮತ್ತು ವಜೀರಾನಿ ಅವರ ಪ್ರತ್ಯೇಕ ಲೆಮ್ಮಾವನ್ನು ಆಧರಿಸಿದೆ. ಅವರು ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಸೆಟ್ಟಿಂಗ್ ಅನ್ನು ಪರಿಗಣಿಸುತ್ತಾರೆ ಮತ್ತು ಇಲ್ಲಿ ಸೆಟ್ಟಿಂಗ್ಗೆ ಅನ್ವಯಿಸುತ್ತಾರೆ, ಇದು ಕೇವಲ ಪ್ರತ್ಯೇಕತೆಯ ಸಂಭವನೀಯತೆಯನ್ನು ನೀಡುತ್ತದೆ. ರಚನಾತ್ಮಕ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತ ಗಣನೆಯ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಪ್ರಮೇಯಗಳು