Circuit satisfiability problem
ಸೈದ್ಧಾಂತಿಕ ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಸರ್ಕ್ಯೂಟ್ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆ (ಇದನ್ನು ಸಿರ್ಕ್ಯೂಟ್-ಸ್ಯಾಟ್, ಸರ್ಕ್ಯೂಟ್ ಸ್ಯಾಟ್, ಸಿಎಸ್ಎಟಿ, ಇತ್ಯಾದಿ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ). ಕೊಟ್ಟಿರುವ ಬೂಲಿಯನ್ ಸರ್ಕ್ಯೂಟ್ ಅದರ ಇನ್ಪುಟ್ಗಳ ನಿಯೋಜನೆಯನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯಾಗಿದ್ದು ಅದು ಔಟ್ಪುಟ್ ಅನ್ನು ನಿಜವಾಗಿಸುತ್ತದೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ನೀಡಲಾದ ಬೂಲಿಯನ್ ಸರ್ಕ್ಯೂಟ್ಗೆ ಇನ್ಪುಟ್ಗಳನ್ನು ಸ್ಥಿರವಾಗಿ 1 ಅಥವಾ 0 ಗೆ ಹೊಂದಿಸಬಹುದೆ ಎಂದು ಅದು ಕೇಳುತ್ತದೆ. ಹಾಗಿದ್ದಲ್ಲಿ, ಸರ್ಕ್ಯೂಟ್ ಅನ್ನು ತೃಪ್ತಿಕರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಇಲ್ಲದಿದ್ದರೆ, ಸರ್ಕ್ಯೂಟ್ ಅನ್ನು ಅತೃಪ್ತಿಕರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಬಲಭಾಗದಲ್ಲಿರುವ ಚಿತ್ರದಲ್ಲಿ, ಎರಡೂ ಇನ್ಪುಟ್ಗಳನ್ನು 1 ಎಂದು ಹೊಂದಿಸುವ ಮೂಲಕ ಎಡ ಸರ್ಕ್ಯೂಟ್ ಅನ್ನು ತೃಪ್ತಿಪಡಿಸಬಹುದು, ಆದರೆ ಬಲ ಸರ್ಕ್ಯೂಟ್ ಅತೃಪ್ತಿಕರವಾಗಿದೆ. ಸರ್ಕ್ಯೂಟ್ ಎಸ್. ಎ. ಟಿ. ಯು ಬೂಲಿಯನ್ ಸೆಟಿಸ್ಫಿಯಾಬಿಲಿಟಿ ಪ್ರಾಬ್ಲೆಮ್ (ಎಸ್. ಎ. ಟಿ.) ಗೆ ನಿಕಟ ಸಂಬಂಧವನ್ನು ಹೊಂದಿದೆ, ಮತ್ತು ಅದೇ ರೀತಿ, ಎನ್. ಪಿ.-ಕಂಪ್ಲೀಟ್ ಎಂದು ಸಾಬೀತಾಗಿದೆ. ಇದು ಒಂದು ಮೂಲಮಾದರಿಯ ಎನ್. ಪಿ.-ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆಯಾಗಿದೆ; ಕುಕ್-ಲೆವಿನ್ ಪ್ರಮೇಯವನ್ನು ಕೆಲವೊಮ್ಮೆ ಎಸ್. ಎ. ಟಿ. ಬದಲಿಗೆ ಸರ್ಕ್ಯೂಟ್ ಎಸ್. ಎ. ಟಿ. ಯಲ್ಲಿ ಸಾಬೀತುಪಡಿಸಲಾಗುತ್ತದೆ, ಮತ್ತು ನಂತರ ಸರ್ಕ್ಯೂಟ್ ಎಸ್. ಎ. ಟಿ. ಅನ್ನು ಅವುಗಳ ಎನ್. ಪಿ.-ಸಂಪೂರ್ಣತೆಯನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಇತರ ತೃಪ್ತಿಕರ ಸಮಸ್ಯೆಗಳಿಗೆ ಕಡಿಮೆ ಮಾಡಬಹುದು. ಅನಿಯಂತ್ರಿತ ಬೈನರಿ ಗೇಟ್ಗಳನ್ನು ಹೊಂದಿರುವ ಸರ್ಕ್ಯೂಟ್ನ ತೃಪ್ತಿಯನ್ನು ಸಮಯಕ್ಕೆ ನಿರ್ಧರಿಸಬಹುದು. ಎನ್ಪಿ-ಸಂಪೂರ್ಣತೆಯ ಪುರಾವೆ ಒಂದು ಸರ್ಕ್ಯೂಟ್ ಮತ್ತು ತೃಪ್ತಿಕರವಾದ ಇನ್ಪುಟ್ಗಳನ್ನು ನೀಡಿದರೆ, ಪ್ರತಿ ಗೇಟ್ನ ಔಟ್ಪುಟ್ ಅನ್ನು ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು. ಆದ್ದರಿಂದ, ಸರ್ಕ್ಯೂಟ್ನ ಔಟ್ಪುಟ್ ಅನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಶೀಲಿಸಬಹುದು. ಹೀಗಾಗಿ ಸರ್ಕ್ಯೂಟ್ ಎಸ್ಎಟಿ ಸಂಕೀರ್ಣತೆ ವರ್ಗ ಎನ್ಪಿಗೆ ಸೇರಿದೆ. ಎನ್ಪಿ-ಗಡಸುತನವನ್ನು ತೋರಿಸಲು, 3ಎಸ್ಎಟಿಯಿಂದ ಸರ್ಕ್ಯೂಟ್ ಎಸ್ಎಟಿಗೆ ಕಡಿತವನ್ನು ನಿರ್ಮಿಸಲು ಸಾಧ್ಯವಿದೆ. ಮೂಲ 3SAT ಸೂತ್ರವು ಅಸ್ಥಿರಗಳನ್ನು ಮತ್ತು ನಿರ್ವಾಹಕರನ್ನು (AND, OR, NOT) ಹೊಂದಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ಪ್ರತಿ ವೇರಿಯೇಬಲ್ಗೆ ಅನುಗುಣವಾದ ಇನ್ಪುಟ್ ಮತ್ತು ಪ್ರತಿ ಆಪರೇಟರ್ಗೆ ಅನುಗುಣವಾದ ಗೇಟ್ ಅನ್ನು ಹೊಂದಿರುವಂತಹ ಸರ್ಕ್ಯೂಟ್ ಅನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸಿ. 3ಎಸ್ಎಟಿ ಸೂತ್ರದ ಪ್ರಕಾರ ಗೇಟ್ಗಳನ್ನು ಸಂಪರ್ಕಿಸಿ. ಉದಾಹರಣೆಗೆ, 3SAT ಸೂತ್ರವು ಸರ್ಕ್ಯೂಟ್ ಆಗಿದ್ದರೆ 3 ಇನ್ಪುಟ್ಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಒಂದು AND, ಒಂದು OR, ಮತ್ತು ಒಂದು ನಾಟ್ ಗೇಟ್. ಇದಕ್ಕೆ ಅನುಗುಣವಾದ ಇನ್ಪುಟ್ ಅನ್ನು AND ಗೇಟ್ಗೆ ಕಳುಹಿಸುವ ಮೊದಲು ತಲೆಕೆಳಗಾಗಿಸಲಾಗುತ್ತದೆ ಮತ್ತು AND ಗೇಟ್ನ ಔಟ್ಪುಟ್ ಅನ್ನು OR ಗೇಟ್ಗೆ ಕಳುಹಿಸಲಾಗುತ್ತದೆ, 3SAT ಸೂತ್ರವು ಮೇಲೆ ವಿನ್ಯಾಸಗೊಳಿಸಲಾದ ಸರ್ಕ್ಯೂಟ್ಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಆದ್ದರಿಂದ ಅವುಗಳ ಔಟ್ಪುಟ್ ಅದೇ ಇನ್ಪುಟ್ಗೆ ಒಂದೇ ಆಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, 3ಎಸ್ಎಟಿ ಸೂತ್ರವು ತೃಪ್ತಿಕರವಾದ ನಿಯೋಜನೆಯನ್ನು ಹೊಂದಿದ್ದರೆ, ಅನುಗುಣವಾದ ಸರ್ಕ್ಯೂಟ್ 1 ಅನ್ನು ಔಟ್ಪುಟ್ ಮಾಡುತ್ತದೆ, ಮತ್ತು ಪ್ರತಿಯಾಗಿ. ಆದ್ದರಿಂದ, ಇದು ಮಾನ್ಯವಾದ ಕಡಿತವಾಗಿದೆ, ಮತ್ತು ಸರ್ಕ್ಯೂಟ್ ಎಸ್ಎಟಿ ಎನ್ಪಿ-ಹಾರ್ಡ್ ಆಗಿದೆ. ಇದು ಸರ್ಕ್ಯೂಟ್ ಎಸ್ಎಟಿ ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಎಂಬುದಕ್ಕೆ ಪುರಾವೆಯನ್ನು ಪೂರ್ಣಗೊಳಿಸುತ್ತದೆ. ನಿರ್ಬಂಧಿತ ರೂಪಾಂತರಗಳು ಮತ್ತು ಸಂಬಂಧಿತ ಸಮಸ್ಯೆಗಳು ಪ್ಲ್ಯಾನರ್ ಸರ್ಕ್ಯೂಟ್ ಎಸ್ಎಟಿ ನಮಗೆ ಪ್ಲ್ಯಾನರ್ ಬೂಲಿಯನ್ ಸರ್ಕ್ಯೂಟ್ ನೀಡಲಾಗಿದೆ ಎಂದು ಭಾವಿಸಿ (ಅಂದರೆ. ಒಂದು ಬೂಲಿಯನ್ ಸರ್ಕ್ಯೂಟ್, ಅದರ ಆಧಾರವಾಗಿರುವ ಗ್ರಾಫ್ ಸಮತಟ್ಟಾಗಿದೆ) ನಿಖರವಾಗಿ ಎರಡು ಇನ್ಪುಟ್ಗಳೊಂದಿಗೆ ಕೇವಲ NAND ಗೇಟ್ಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಪ್ಲ್ಯಾನರ್ ಸರ್ಕ್ಯೂಟ್ ಎಸ್ಎಟಿ ಎಂಬುದು ಈ ಸರ್ಕ್ಯೂಟ್ ತನ್ನ ಇನ್ಪುಟ್ಗಳ ನಿಯೋಜನೆಯನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯಾಗಿದ್ದು ಅದು ಔಟ್ಪುಟ್ ಅನ್ನು ನಿಜವಾಗಿಸುತ್ತದೆ. ಈ ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿದೆ. ಇದಲ್ಲದೆ, ಸರ್ಕ್ಯೂಟ್ನಲ್ಲಿನ ಯಾವುದೇ ಗೇಟ್ ಎನ್ಒಆರ್ ಗೇಟ್ ಆಗುವಂತೆ ನಿರ್ಬಂಧಗಳನ್ನು ಬದಲಾಯಿಸಿದರೆ, ಪರಿಣಾಮವಾಗಿ ಉಂಟಾಗುವ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿ ಉಳಿಯುತ್ತದೆ. ಯು. ಎನ್. ಎಸ್. ಎ. ಟಿ. ಸರ್ಕ್ಯೂಟ್ ಯು. ಎನ್. ಎಸ್. ಎ. ಟಿ. ಯು ಒಂದು ನಿರ್ದಿಷ್ಟ ಬೂಲಿಯನ್ ಸರ್ಕ್ಯೂಟ್ ತನ್ನ ಇನ್ಪುಟ್ಗಳ ಎಲ್ಲಾ ಸಂಭಾವ್ಯ ನಿಯೋಜನೆಗಳಿಗೆ ತಪ್ಪು ಔಟ್ಪುಟ್ಗಳನ್ನು ನೀಡುತ್ತದೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಇದು ಸರ್ಕ್ಯೂಟ್ ಎಸ್ಎಟಿ ಸಮಸ್ಯೆಯ ಪೂರಕವಾಗಿದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಕೋ-ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ. ಸರ್ಕ್ಯೂಟ್ಸ್ಯಾಟ್ ಅಥವಾ ಅದರ ರೂಪಾಂತರಗಳಿಂದ ಸರ್ಕ್ಯೂಟ್ಸ್ಯಾಟ್ ಕಡಿತದಿಂದ ಕಡಿತವನ್ನು ಕೆಲವು ಸಮಸ್ಯೆಗಳ ಎನ್ಪಿ-ಗಡಸುತನವನ್ನು ತೋರಿಸಲು ಬಳಸಬಹುದು, ಮತ್ತು ನಮಗೆ ಡ್ಯುಯಲ್-ರೈಲ್ ಮತ್ತು ಬೈನರಿ ಲಾಜಿಕ್ ಕಡಿತಗಳಿಗೆ ಪರ್ಯಾಯವನ್ನು ಒದಗಿಸುತ್ತದೆ. ಅಂತಹ ಕಡಿತವು ನಿರ್ಮಿಸಬೇಕಾದ ಸಾಧನಗಳೆಂದರೆಃ ಒಂದು ತಂತಿ ಸಾಧನ. ಈ ಗ್ಯಾಜೆಟ್ ಸರ್ಕ್ಯೂಟ್ನಲ್ಲಿರುವ ತಂತಿಗಳನ್ನು ಅನುಕರಿಸುತ್ತದೆ. ಒಂದು ವಿಭಜಿತ ಸಾಧನ. ಈ ಗ್ಯಾಜೆಟ್ ಎಲ್ಲಾ ಔಟ್ಪುಟ್ ತಂತಿಗಳು ಇನ್ಪುಟ್ ತಂತಿಯಂತೆಯೇ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿವೆ ಎಂದು ಖಾತರಿಪಡಿಸುತ್ತದೆ. ಸರ್ಕ್ಯೂಟ್ನ ಗೇಟ್ಗಳನ್ನು ಅನುಕರಿಸುವ ಗ್ಯಾಜೆಟ್ಗಳು. ನಿಜವಾದ ಟರ್ಮಿನೇಟರ್ ಗ್ಯಾಜೆಟ್. ಈ ಗ್ಯಾಜೆಟ್ ಅನ್ನು ಇಡೀ ಸರ್ಕ್ಯೂಟ್ನ ಔಟ್ಪುಟ್ ಅನ್ನು ಟ್ರೂ ಎಂದು ಒತ್ತಾಯಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ. ಒಂದು ಟರ್ನ್ ಗ್ಯಾಜೆಟ್. ಈ ಗ್ಯಾಜೆಟ್ ನಮಗೆ ಅಗತ್ಯವಿರುವಂತೆ ಸರಿಯಾದ ದಿಕ್ಕಿನಲ್ಲಿ ತಂತಿಗಳನ್ನು ಮರುನಿರ್ದೇಶಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಕ್ರಾಸ್ಒವರ್ ಗ್ಯಾಜೆಟ್. ಈ ಗ್ಯಾಜೆಟ್ ನಮಗೆ ಎರಡು ತಂತಿಗಳು ಪರಸ್ಪರ ಸಂವಹನ ಮಾಡದೆ ಪರಸ್ಪರ ದಾಟಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಮೈನ್ಸ್ವೀಪರ್ ಇನ್ಫೆರೆನ್ಸ್ ಪ್ರಾಬ್ಲಮ್ ಈ ಸಮಸ್ಯೆಯು ಮೈನ್ಸ್ವೀಪರ್ ಬೋರ್ಡ್ ನೀಡಿದ ಎಲ್ಲಾ ಬಾಂಬ್ಗಳನ್ನು ಪತ್ತೆಹಚ್ಚಲು ಸಾಧ್ಯವೇ ಎಂದು ಕೇಳುತ್ತದೆ. ಸರ್ಕ್ಯೂಟ್ ಯುಎನ್ಎಸ್ಎಟಿ ಸಮಸ್ಯೆಯಿಂದ ಕಡಿಮೆಯಾಗುವ ಮೂಲಕ ಇದು ಸಿಒಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಎಂದು ಸಾಬೀತಾಗಿದೆ. ಈ ಕಡಿತಕ್ಕಾಗಿ ನಿರ್ಮಿಸಲಾದ ಸಾಧನಗಳೆಂದರೆಃ ತಂತಿ, ಸ್ಪ್ಲಿಟ್, ಮತ್ತು ನಾಟ್ ಗೇಟ್ಸ್ ಮತ್ತು ಟರ್ಮಿನೇಟರ್. ಈ ಸಾಧನಗಳಿಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಮೂರು ನಿರ್ಣಾಯಕ ಅವಲೋಕನಗಳಿವೆ. ಮೊದಲನೆಯದಾಗಿ, ಸ್ಪ್ಲಿಟ್ ಗ್ಯಾಜೆಟ್ ಅನ್ನು ನಾಟ್ ಗ್ಯಾಜೆಟ್ ಮತ್ತು ಟರ್ನ್ ಗ್ಯಾಜೆಟ್ ಆಗಿಯೂ ಬಳಸಬಹುದು. ಎರಡನೆಯದಾಗಿ, ಆಂಡ್ ಮತ್ತು ನಾಟ್ ಗ್ಯಾಜೆಟ್ಗಳನ್ನು ನಿರ್ಮಿಸುವುದು ಸಾಕು, ಏಕೆಂದರೆ ಅವು ಒಟ್ಟಾಗಿ ಸಾರ್ವತ್ರಿಕ ನ್ಯಾಂಡ್ ಗೇಟ್ ಅನ್ನು ಅನುಕರಿಸಬಹುದು. ಅಂತಿಮವಾಗಿ, XOR ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಲು ಮೂರು NAND ಗಳನ್ನು ಛೇದಕ-ಮುಕ್ತವಾಗಿ ರಚಿಸಬಹುದಾದ್ದರಿಂದ, ಮತ್ತು ಕ್ರಾಸ್ಒವರ್ ಅನ್ನು ನಿರ್ಮಿಸಲು XOR ಸಾಕಾಗುವುದರಿಂದ, ಇದು ನಮಗೆ ಅಗತ್ಯವಾದ ಕ್ರಾಸ್ಒವರ್ ಗ್ಯಾಜೆಟ್ ಅನ್ನು ನೀಡುತ್ತದೆ. ತ್ಸೆಟಿನ್ ರೂಪಾಂತರವು ಸರ್ಕ್ಯೂಟ್-ಎಸ್ಎಟಿಯಿಂದ ಎಸ್ಎಟಿಗೆ ನೇರವಾದ ಕಡಿತವಾಗಿದೆ. ಸರ್ಕ್ಯೂಟ್ ಅನ್ನು ಸಂಪೂರ್ಣವಾಗಿ 2-ಇನ್ಪುಟ್ NAND ಗೇಟ್ಗಳಿಂದ (ಬೂಲಿಯನ್ ಆಪರೇಟರ್ಗಳ ಕ್ರಿಯಾತ್ಮಕವಾಗಿ-ಪೂರ್ಣವಾದ ಸೆಟ್) ನಿರ್ಮಿಸಲಾಗಿದೆಯೇ ಎಂದು ವಿವರಿಸಲು ಸುಲಭವಾಗಿದೆಃ ಸರ್ಕ್ಯೂಟ್ನಲ್ಲಿನ ಪ್ರತಿ ನಿವ್ವಳಕ್ಕೆ ವೇರಿಯೇಬಲ್ ಅನ್ನು ನಿಯೋಜಿಸಿ, ನಂತರ ಪ್ರತಿ NAND ಗೇಟ್ಗೆ, ಕಾಂಜಂಕ್ಟಿವ್ ನಾರ್ಮಲ್ ಫಾರ್ಮ್ ಷರತ್ತುಗಳನ್ನು ನಿರ್ಮಿಸಿ (v1⁄v3) ′ (v2⁄v3) ′ (¬v1·v2·v3), ಅಲ್ಲಿ v1 ಮತ್ತು v2 NAND ಗೇಟ್ಗೆ ಇನ್ಪುಟ್ಗಳಾಗಿವೆ ಮತ್ತು v3 ಔಟ್ಪುಟ್ ಆಗಿದೆ. ಈ ಷರತ್ತುಗಳು ಮೂರು ಅಸ್ಥಿರಗಳ ನಡುವಿನ ಸಂಬಂಧವನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ವಿವರಿಸುತ್ತವೆ. ಸರ್ಕ್ಯೂಟ್ನ ಔಟ್ಪುಟ್ ವೇರಿಯೇಬಲ್ ಅನ್ನು ನಿಜವೆಂದು ನಿರ್ಬಂಧಿಸುವ ಹೆಚ್ಚುವರಿ ಷರತ್ತಿನೊಂದಿಗೆ ಎಲ್ಲಾ ಗೇಟ್ಗಳಿಂದ ಷರತ್ತುಗಳನ್ನು ಜೋಡಿಸುವುದು ಕಡಿತವನ್ನು ಪೂರ್ಣಗೊಳಿಸುತ್ತದೆ; ಮೂಲ ಸರ್ಕ್ಯೂಟ್ ತೃಪ್ತಿಕರವಾಗಿದ್ದರೆ ಮತ್ತು ಯಾವುದೇ ಪರಿಹಾರವು ಸರ್ಕ್ಯೂಟ್ ಔಟ್ಪುಟ್ ಅನ್ನು ಮಾಡುವ ಇನ್ಪುಟ್ಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವ ಮೂಲ ಸಮಸ್ಯೆಗೆ ಪರಿಹಾರವಾಗಿದ್ದರೆ ಮಾತ್ರ ಎಲ್ಲಾ ನಿರ್ಬಂಧಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ವೇರಿಯೇಬಲ್ಗಳ ನಿಯೋಜನೆ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ. ಇದಕ್ಕೆ ತದ್ವಿರುದ್ಧವಾದ-SAT ಅನ್ನು ಸರ್ಕ್ಯೂಟ್-SAT ಗೆ ಕಡಿತಗೊಳಿಸಬಹುದು-ಬೂಲಿಯನ್ ಸೂತ್ರವನ್ನು ಸರ್ಕ್ಯೂಟ್ ಆಗಿ ಪುನಃ ಬರೆಯುವ ಮೂಲಕ ಮತ್ತು ಅದನ್ನು ಪರಿಹರಿಸುವ ಮೂಲಕ ಕ್ಷುಲ್ಲಕವಾಗಿ ಅನುಸರಿಸುತ್ತದೆ. ಸರ್ಕ್ಯೂಟ್ ವ್ಯಾಲ್ಯೂ ಪ್ರಾಬ್ಲಮ್ ಸ್ಟ್ರಕ್ಚರ್ಡ್ ಸರ್ಕ್ಯೂಟ್ ಸ್ಯಾಟಿಸಫೈಬಿಲಿಟಿ ಸ್ಯಾಟಿಸಫೈಬಿಲಿಟಿ ಪ್ರಾಬ್ಲಮ್ ಉಲ್ಲೇಖಗಳು ಎನ್. ಪಿ-ಕಂಪ್ಲೀಟ್ ಪ್ರಾಬ್ಲಮ್ಸ್ ಕಂಪ್ಯೂಟೇಶನಲ್ ಪ್ರಾಬ್ಲಮ್ಸ್ ಕಂಪ್ಯೂಟೇಬಿಲಿಟಿ ಥಿಯರಿಯನ್ನು ಸಹ ನೋಡಿ.