MAX-3SAT
ಮ್ಯಾಕ್ಸ್-3ಸ್ಯಾಟ್ ಎಂಬುದು ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನದ ಗಣನೆಯ ಸಂಕೀರ್ಣತೆಯ ಉಪಕ್ಷೇತ್ರದಲ್ಲಿರುವ ಒಂದು ಸಮಸ್ಯೆಯಾಗಿದೆ. ಇದು ಸಂಕೀರ್ಣತೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಪರಿಗಣಿಸಲಾದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯಾದ ಬೂಲಿಯನ್ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಯನ್ನು (ಎಸ್ಎಟಿ) ಸಾಮಾನ್ಯೀಕರಿಸುತ್ತದೆ. ಇದನ್ನು ಹೀಗೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆಃ 3-ಸಿ. ಎನ್. ಎಫ್ ಸೂತ್ರವನ್ನು ನೀಡಿದರೆ (ಅಂದರೆ. ಪ್ರತಿ ಷರತ್ತಿಗೆ ಗರಿಷ್ಠ 3 ಅಸ್ಥಿರಗಳೊಂದಿಗೆ), ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ಷರತ್ತುಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ನಿಯೋಜನೆಯನ್ನು ಹುಡುಕಿ. MAX-3SAT ಎಂಬುದು ಸಂಕೀರ್ಣತೆಯ ವರ್ಗವಾದ MAXSNPಗೆ ಸಂಬಂಧಿಸಿದ ಒಂದು ಅಂಗೀಕೃತ ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆಯಾಗಿದೆ (ಪಾಪಡಿಮಿಟ್ರಿಯೊ pgಯಲ್ಲಿ ಪೂರ್ಣವಾಗಿ ತೋರಿಸಲಾಗಿದೆ. 314). ಅಂದಾಜು MAX-3SATಯ ನಿರ್ಧಾರದ ಆವೃತ್ತಿಯು NP-ಪೂರ್ಣವಾಗಿದೆ. ಆದ್ದರಿಂದ, P = NP ಇದ್ದರೆ ಮಾತ್ರ ಬಹುಪದ-ಸಮಯದ ಪರಿಹಾರವನ್ನು ಸಾಧಿಸಬಹುದು. ಆದಾಗ್ಯೂ, ಈ ಸರಳ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ 2 ರ ಅಂಶದೊಳಗಿನ ಅಂದಾಜನ್ನು ಸಾಧಿಸಬಹುದುಃ ಎಲ್ಲಾ ಅಸ್ಥಿರಗಳು = TRUE ಅಥವಾ ಎಲ್ಲಾ ಅಸ್ಥಿರಗಳು = FALSE ಆಗಿರುವಾಗ, ಹೆಚ್ಚಿನ ಷರತ್ತುಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ಪರಿಹಾರವನ್ನು ಔಟ್ಪುಟ್ ಮಾಡಿ. ಪ್ರತಿಯೊಂದು ಷರತ್ತು ಎರಡು ಪರಿಹಾರಗಳಲ್ಲಿ ಒಂದರಿಂದ ತೃಪ್ತಿಯಾಗಿದೆ, ಆದ್ದರಿಂದ ಒಂದು ಪರಿಹಾರವು ಕನಿಷ್ಠ ಅರ್ಧದಷ್ಟು ಷರತ್ತುಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ. ಕಾರ್ಲೋಫ್-ಝ್ವಿಕ್ ಅಲ್ಗಾರಿದಮ್ ಬಹುಪದ-ಸಮಯದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಮತ್ತು ಷರತ್ತುಗಳ 7/8 ಅನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಯಾದೃಚ್ಛಿಕಗೊಳಿಸಲಾಗಿದ್ದರೂ, ಅದೇ ಅಂದಾಜು ಖಾತರಿಗಳೊಂದಿಗೆ ನಿರ್ಣಾಯಕ (ಬಹುಪದ-ಸಮಯ) ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೀಡುವ ತಂತ್ರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಅದನ್ನು ಬೇರ್ಪಡಿಸಬಹುದು. ಪ್ರಮೇಯ 1 (ಅಸಮರ್ಪಕತೆ) ಮ್ಯಾಕ್ಸ್-3ಎಸ್ಎಟಿಯ (MAX-3SAT)-ಸಾಮೀಪ್ಯವು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿರುವಂತಹ ε> 0 ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ ಎಂದು ಪಿಸಿಪಿ ಪ್ರಮೇಯವು ಸೂಚಿಸುತ್ತದೆ. ಪುರಾವೆಃ ಪಿ. ಸಿ. ಪಿ. ಪ್ರಮೇಯದ ಪ್ರಕಾರ ಯಾವುದೇ ಎನ್. ಪಿ.-ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆ. x ω L ಗೆ, 3-CNF ಸೂತ್ರವನ್ನು ನಿರ್ಮಿಸಲಾಗಿದೆ, ಇದರಿಂದಾಗಿ x ω L ωx ತೃಪ್ತಿಕರವಾಗಿದೆ x ω L ωx ನ (1-ε) m ಷರತ್ತುಗಳಿಗಿಂತ ಹೆಚ್ಚಿಲ್ಲ. ವೆರಿಫೈರ್ ವಿ ಎಲ್ಲಾ ಅಗತ್ಯ ಬಿಟ್ಗಳನ್ನು ಏಕಕಾಲದಲ್ಲಿ ಓದುತ್ತದೆ. ಹೊಂದಾಣಿಕೆಯಾಗದ ಪ್ರಶ್ನೆಗಳನ್ನು ಮಾಡುತ್ತದೆ. ಇದು ಮಾನ್ಯವಾಗಿದೆ ಏಕೆಂದರೆ ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ. q ಎಂಬುದು ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆಯಾಗಿರಲಿ. ಎಲ್ಲಾ ಯಾದೃಚ್ಛಿಕ ತಂತಿಗಳನ್ನು Ri ωV ಎಂದು ಎಣಿಸಿದಾಗ, ನಾವು ಪ್ರತಿ ತಂತಿಯ ಉದ್ದದಿಂದ ಪಾಲಿ (x) ತಂತಿಗಳನ್ನು ಪಡೆಯುತ್ತೇವೆ. ಪ್ರತಿ ರಿ ವಿ ಗೆ q ಸ್ಥಾನಗಳು i1,., iq ಮತ್ತು ಬೂಲಿಯನ್ ಕಾರ್ಯ fR: {0,1} q-> {0,1} ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ ಮತ್ತು fR (π (i1,., iq)) ಆಗಿದ್ದರೆ ಮಾತ್ರ ಸ್ವೀಕರಿಸುತ್ತದೆ. ಇಲ್ಲಿ π ಎಂಬುದು ಒರಾಕಲ್ನಿಂದ ಪಡೆದ ಪುರಾವೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಮುಂದೆ ನಾವು ಇದನ್ನು ಅನುಕರಿಸಲು ಬೂಲಿಯನ್ ಸೂತ್ರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ. ನಾವು ಬೂಲಿಯನ್ ಅಸ್ಥಿರಗಳಾದ x1,., xl ಅನ್ನು ಪರಿಚಯಿಸುತ್ತೇವೆ, ಅಲ್ಲಿ l ಎಂಬುದು ಪುರಾವೆಯ ಉದ್ದವಾಗಿದೆ. ವೆರಿಫೈರ್ ಸಂಭಾವ್ಯ ಬಹುಪದ-ಸಮಯದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಎಂದು ತೋರಿಸಲು, ತೃಪ್ತಿಕರವಾದ ಷರತ್ತುಗಳ ಸಂಖ್ಯೆ ಮತ್ತು ವೆರಿಫೈರ್ ಸ್ವೀಕರಿಸುವ ಸಂಭವನೀಯತೆಯ ನಡುವೆ ನಮಗೆ ಪತ್ರವ್ಯವಹಾರದ ಅಗತ್ಯವಿದೆ. ಪ್ರತಿ ಆರ್ ಗೆ, 2 ಕ್ಯೂ ಎಸ್ಎಟಿ ಷರತ್ತುಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಎಫ್ಆರ್ (xi1,., xiq) ಅನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಷರತ್ತುಗಳನ್ನು ಸೇರಿಸಿ. ಉದ್ದ q ನ ಷರತ್ತುಗಳನ್ನು ಹೊಸ (ಸಹಾಯಕ) ಅಸ್ಥಿರಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಉದ್ದ 3 ಕ್ಕೆ ಪರಿವರ್ತಿಸಲಾಗುತ್ತದೆ. x2 * x10 * x11 * x12 = (x2 * x10 * yR) (R * x11 * x12). ಇದಕ್ಕೆ ಗರಿಷ್ಠ q2q 3-SAT ಷರತ್ತುಗಳು ಬೇಕಾಗುತ್ತವೆ. z ω L ಆಗಿದ್ದರೆ, ಪ್ರತಿ Ri ಗೆ Vπ (z) ಸ್ವೀಕರಿಸುವಂತಹ ಒಂದು ಪುರಾವೆ π ಇರುತ್ತದೆ. xi = π (i) ಮತ್ತು ಸಹಾಯಕ ಅಸ್ಥಿರಗಳನ್ನು ಸರಿಯಾಗಿ ಸೇರಿಸಿದರೆ ಎಲ್ಲಾ ಷರತ್ತುಗಳು ತೃಪ್ತಿಯಾಗುತ್ತವೆ. x1,., xl ಮತ್ತು yR ಗಳ ಪ್ರತಿ ನಿಯೋಜನೆಗೆ, ಅನುಗುಣವಾದ ಪುರಾವೆ π (i) = xi ಎಲ್ಲಾ R bul {0,1} r (|z |) ನ ಅರ್ಧಕ್ಕೆ ಪರಿಶೀಲಕನನ್ನು ತಿರಸ್ಕರಿಸುವಂತೆ ಮಾಡುತ್ತದೆ. ಪ್ರತಿ ಆರ್ ಗೆ, ಎಫ್ಆರ್ ಅನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಒಂದು ಷರತ್ತು ವಿಫಲಗೊಳ್ಳುತ್ತದೆ. ಆದ್ದರಿಂದ, ಷರತ್ತುಗಳ ಒಂದು ಭಾಗವು ವಿಫಲಗೊಳ್ಳುತ್ತದೆ. ಇದು ಪ್ರತಿ ಎನ್. ಪಿ.-ಪೂರ್ಣ ಸಮಸ್ಯೆಗೂ ಅನ್ವಯಿಸಿದರೆ, ಪಿ. ಸಿ. ಪಿ. ಪ್ರಮೇಯವು ನಿಜವಾಗಿರಬೇಕು ಎಂದು ತೀರ್ಮಾನಿಸಬಹುದು. ಪ್ರಮೇಯ 2 ಹಾಸ್ಟಾಡ್ ಪ್ರಮೇಯ 1 ಗಿಂತ ಕಠಿಣವಾದ ಫಲಿತಾಂಶವನ್ನು ಪ್ರದರ್ಶಿಸುತ್ತದೆ. ε ಗೆ ಅತ್ಯಂತ ಪ್ರಸಿದ್ಧವಾದ ಮೌಲ್ಯ. ಅವರು 3-ಎಸ್ಎಟಿಗಾಗಿ ಪಿಸಿಪಿ ವೆರಿಫೈರ್ ಅನ್ನು ನಿರ್ಮಿಸುತ್ತಾರೆ, ಅದು ಪ್ರೂಫ್ನಿಂದ ಕೇವಲ 3 ಬಿಟ್ಗಳನ್ನು ಮಾತ್ರ ಓದುತ್ತದೆ. ಪ್ರತಿ ε> 0 ಗೆ, 3-SAT ಗೆ ಪಿಸಿಪಿ-ವೆರಿಫೈಯರ್ M ಇದೆ, ಅದು ಯಾದೃಚ್ಛಿಕ ಸ್ಟ್ರಿಂಗ್ r ಉದ್ದವನ್ನು ಓದುತ್ತದೆ ಮತ್ತು ಪ್ರೂಫ್ π ಮತ್ತು ಬಿಟ್ ಬಿಆರ್ ನಲ್ಲಿ ಐಆರ್, ಜೆಆರ್, ಕೆಆರ್ ಪ್ರಶ್ನೆಯ ಸ್ಥಾನಗಳನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತದೆ. ಪರಿಶೀಲನಾ ಯಂತ್ರವು ಸಂಪೂರ್ಣತೆ (1−ε) ಮತ್ತು ದೃಢತೆ (ಪಿಸಿಪಿ (ಸಂಕೀರ್ಣತೆ) ಯನ್ನು ಉಲ್ಲೇಖಿಸಿ) ಯನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಅದು ಸ್ವೀಕರಿಸುತ್ತದೆ. ಈ ಎರಡು ಸಮೀಕರಣಗಳಲ್ಲಿ ಮೊದಲನೆಯದನ್ನು ಎಂದಿನಂತೆ "= 1" ಎಂದು ಸಮೀಕರಿಸಿದರೆ, P = NP ಅನ್ನು ಸೂಚಿಸುವ ರೇಖೀಯ ಸಮೀಕರಣಗಳ ವ್ಯವಸ್ಥೆಯನ್ನು ಪರಿಹರಿಸುವ ಮೂಲಕ π ಪುರಾವೆಯನ್ನು ಕಂಡುಹಿಡಿಯಬಹುದು (MAX-3LIN-EQN ಅನ್ನು ನೋಡಿ). ಒಂದು ವೇಳೆ z ω L ಆಗಿದ್ದರೆ, ಷರತ್ತುಗಳ ಒಂದು ಭಾಗವು (1 − ε) ತೃಪ್ತಿಯಾಗುತ್ತದೆ. z′L ಆಗಿದ್ದರೆ, Rನ ಒಂದು (1/2−ε) ಭಾಗಕ್ಕೆ, 1/4 ಷರತ್ತುಗಳು ವಿರೋಧಿಸಲ್ಪಡುತ್ತವೆ. ಅಂದಾಜು ಅನುಪಾತದ ಗಡಸುತನವನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಇದು ಸಾಕಾಗುತ್ತದೆ ಸಂಬಂಧಿತ ಸಮಸ್ಯೆಗಳು MAX-3SAT (B) ಎಂಬುದು MAX-3SAT ನ ನಿರ್ಬಂಧಿತ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆ, ಅಲ್ಲಿ ಪ್ರತಿ ವೇರಿಯೇಬಲ್ ಗರಿಷ್ಠ B ಷರತ್ತುಗಳಲ್ಲಿ ಕಂಡುಬರುತ್ತದೆ. ಪಿಸಿಪಿ ಪ್ರಮೇಯವನ್ನು ಸಾಬೀತುಪಡಿಸುವ ಮೊದಲು, ಕೆಲವು ಸ್ಥಿರ ಸ್ಥಿರಾಂಕ ಬಿ ಗೆ, ಈ ಸಮಸ್ಯೆಯು ಮ್ಯಾಕ್ಸ್ ಎಸ್ಎನ್ಪಿ-ಕಠಿಣವಾಗಿದೆ ಎಂದು ಪಾಪಾಡಿಮಿಟ್ರಿಯು ಮತ್ತು ಯನ್ನಾಕಾಕಿಸ್ ತೋರಿಸಿದರು. ಇದರ ಪರಿಣಾಮವಾಗಿ, ಪಿಸಿಪಿ ಪ್ರಮೇಯದೊಂದಿಗೆ, ಇದು ಎಪಿಎಕ್ಸ್-ಹಾರ್ಡ್ ಆಗಿದೆ. ಇದು ಉಪಯುಕ್ತವಾಗಿದೆ ಏಕೆಂದರೆ ಮ್ಯಾಕ್ಸ್-3ಎಸ್ಎಟಿಗೆ ಸಾಧ್ಯವಾಗದ ರೀತಿಯಲ್ಲಿ ಪಿಟಿಎಎಸ್-ಸಂರಕ್ಷಣಾ ಕಡಿತವನ್ನು ಪಡೆಯಲು ಮ್ಯಾಕ್ಸ್-3ಎಸ್ಎಟಿ (ಬಿ) ಅನ್ನು ಹೆಚ್ಚಾಗಿ ಬಳಸಬಹುದು. ಬಿ ಯ ಸ್ಪಷ್ಟ ಮೌಲ್ಯಗಳಿಗೆ ಪುರಾವೆಗಳು ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಒಳಗೊಂಡಿವೆಃ ಎಲ್ಲಾ ಬಿ ± 13, ಸಂಜೀವ್ ಅರೋರಾ, "ಪ್ರೂಫ್ಸ್ ಮತ್ತು ಹಾರ್ಡ್ನೆಸ್ ಆಫ್ ಅಪ್ರಾಕ್ಸಿಮೇಷನ್ ಪ್ರಾಬ್ಲಮ್ಸ್ನ ಸಂಭವನೀಯ ಪರಿಶೀಲನೆ", ಆಗಸ್ಟ್ 1994 ರಲ್ಲಿ ಯು. ಸಿ. ಬರ್ಕ್ಲಿಯ ಸಿಎಸ್ ವಿಭಾಗದಲ್ಲಿ ಸಲ್ಲಿಸಲಾದ ಪ್ರಬಂಧದ ಪರಿಷ್ಕೃತ ಆವೃತ್ತಿ. CS-TR-476-94. ವಿಭಾಗ 7.2. ಮತ್ತು ಎಲ್ಲಾ ಬಿ ≤3 (ಇದು ಸಾಧ್ಯವಾದಷ್ಟು ಉತ್ತಮವಾಗಿದೆ). ಇದಲ್ಲದೆ, 2ಎಸ್ಎಟಿ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದಾದರೂ, ಮ್ಯಾಕ್ಸ್-2ಎಸ್ಎಟಿ (3) ಸಹ ಎಪಿಎಕ್ಸ್-ಕಠಿಣವಾಗಿದೆ. ಎನ್. ಪಿ. = ಆರ್. ಪಿ. ಹೊರತು, ಬಿ. ಯ ಕಾರ್ಯವಾಗಿ ಮ್ಯಾಕ್ಸ್-3ಎಸ್ಎಟಿ (ಬಿ) ಗೆ ಸಾಧ್ಯವಾದಷ್ಟು ಉತ್ತಮ ಅಂದಾಜು ಅನುಪಾತವು ಕನಿಷ್ಠ ಮತ್ತು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. ಬಿ ಯ ಕೆಲವು ಮೌಲ್ಯಗಳಿಗೆ ಅಂದಾಜು ಸ್ಥಿರಾಂಕಗಳ ಮೇಲೆ ಕೆಲವು ಸ್ಪಷ್ಟ ಮಿತಿಗಳು ತಿಳಿದಿವೆ. ಮ್ಯಾಕ್ಸ್-3ಎಸ್ಎಟಿಯ "ನಿರ್ಣಾಯಕ" ನಿದರ್ಶನಗಳಲ್ಲಿ ಪ್ರತಿ ಅಕ್ಷರಶಃ ನಿಖರವಾಗಿ ಎರಡು ಬಾರಿ ಸಂಭವಿಸುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಷರತ್ತು ನಿಖರವಾಗಿ ಗಾತ್ರ 3 ರಷ್ಟಿದೆ ಎಂದು ಬರ್ಮನ್, ಕಾರ್ಪಿನ್ಸ್ಕಿ ಮತ್ತು ಸ್ಕಾಟ್ ಸಾಬೀತುಪಡಿಸಿದರು, ಕೆಲವು ಸ್ಥಿರ ಅಂಶಗಳಿಗೆ ಸಮಸ್ಯೆಯು ಅಂದಾಜು ಕಠಿಣವಾಗಿದೆ. MAX-EkSAT ಎಂಬುದು MAX-3SAT ನ ನಿಯತಾಂಕಗೊಳಿಸಿದ ಆವೃತ್ತಿಯಾಗಿದ್ದು, ಅಲ್ಲಿ ಪ್ರತಿ ಷರತ್ತು ನಿಖರವಾಗಿ ಅಕ್ಷರಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಕೋಡಿಂಗ್ ಸಿದ್ಧಾಂತದ ಕಲ್ಪನೆಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಅಂದಾಜು ಅನುಪಾತದೊಂದಿಗೆ ಇದನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಅಂದಾಜು ಮಾಡಬಹುದು. ಮ್ಯಾಕ್ಸ್-3ಎಸ್ಎಟಿಯ ಯಾದೃಚ್ಛಿಕ ನಿದರ್ಶನಗಳನ್ನು ಅಂಶದೊಳಗೆ ಅಂದಾಜು ಮಾಡಬಹುದು ಎಂದು ಸಾಬೀತಾಗಿದೆ. ಕ್ಯಾಲಿಫೋರ್ನಿಯಾ ವಿಶ್ವವಿದ್ಯಾನಿಲಯ, ಬರ್ಕ್ಲಿಯ ಕೋಡಿಂಗ್ ಸಿದ್ಧಾಂತದ ಟಿಪ್ಪಣಿಗಳು ಬಫಲೋ ವಿಶ್ವವಿದ್ಯಾನಿಲಯದ ಕೋಡಿಂಗ್ ಸಿದ್ಧಾಂತವು ಎನ್. ಪಿ.-ಹಾರ್ಡ್ ಸಮಸ್ಯೆಗಳ ಬಗ್ಗೆ ಹೇಳುತ್ತದೆ.