Tentai Show
ಟೆಂಟೈಶೋ, ಗ್ಯಾಲಕ್ಸಿಸ್, ಸ್ಪೈರಲ್ ಗ್ಯಾಲಕ್ಸಿಸ್, ಅಥವಾ ಸಿಮ್-ಎ-ಪಿಕ್ಸ್ ಎಂಬ ಹೆಸರುಗಳಿಂದಲೂ ಕರೆಯಲ್ಪಡುವ ಟೆಂಟೈ ಶೋ (ಜಪಾನೀಸ್ಃ ಟೆಂಟೈ ಶೋ), ನಿಕೋಲಿ ಪ್ರಕಟಿಸಿದ ಬೈನರಿ-ಡಿಟರ್ಮಿನೇಷನ್ ಲಾಜಿಕ್ ಒಗಟು. ನಿಯಮಗಳ ಟೆಂಟಾಯ್ ಪ್ರದರ್ಶನವನ್ನು ಚೌಕಗಳ ಆಯತಾಕಾರದ ಗ್ರಿಡ್ನಲ್ಲಿ ಆಡಲಾಗುತ್ತದೆ. ಗ್ರಿಡ್ನಲ್ಲಿ ನಕ್ಷತ್ರಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಚುಕ್ಕೆಗಳಿರುತ್ತವೆ, ಇವು ಗ್ರಿಡ್ನಲ್ಲಿ ಕೋಶದ ಮಧ್ಯಭಾಗದಲ್ಲಿ, ಅಂಚಿನಲ್ಲಿ ಅಥವಾ ಮೂಲೆಯಲ್ಲಿ ಕಂಡುಬರುತ್ತವೆ. ಗ್ರಿಡ್ ಅನ್ನು ನಕ್ಷತ್ರಪುಂಜಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಪ್ರದೇಶಗಳಾಗಿ ವಿಂಗಡಿಸಲು ಡ್ಯಾಶ್ ಮಾಡಿದ ರೇಖೆಗಳ ಉದ್ದಕ್ಕೂ ರೇಖೆಗಳನ್ನು ಎಳೆಯುವುದು ಒಗಟಿನ ಉದ್ದೇಶವಾಗಿದೆ. ಪರಿಣಾಮವಾಗಿ ಬರುವ ಗ್ರಿಡ್ನಲ್ಲಿ, ಎಲ್ಲಾ ನಕ್ಷತ್ರಪುಂಜಗಳು 180° ತಿರುಗುವಿಕೆಯ ಸಮ್ಮಿತಿಯನ್ನು ಹೊಂದಿರಬೇಕು ಮತ್ತು ಅದರ ಕೇಂದ್ರದಲ್ಲಿ ನಿಖರವಾಗಿ ಒಂದು ಚುಕ್ಕೆಯನ್ನು ಹೊಂದಿರಬೇಕು. ಚುಕ್ಕೆಗಳ ಬಣ್ಣಗಳು ಒಗಟಿನ ತರ್ಕದ ಮೇಲೆ ಪರಿಣಾಮ ಬೀರುವುದಿಲ್ಲ ಮತ್ತು ಪರಿಹರಿಸುವಾಗ ನಿರ್ಲಕ್ಷಿಸಬಹುದು. ಅನೇಕ ಬಣ್ಣದ ಚುಕ್ಕೆಗಳಿರುವ ಒಗಟುಗಳಲ್ಲಿ, ಚಿತ್ರವನ್ನು ಬಹಿರಂಗಪಡಿಸಲು ಪೂರ್ಣಗೊಂಡ ಗ್ರಿಡ್ನ ಪ್ರದೇಶಗಳನ್ನು ಅನುಗುಣವಾದ ಚುಕ್ಕೆಗಳ ಬಣ್ಣಗಳಿಂದ ಬಣ್ಣ ಮಾಡಬಹುದು. ಪರಿಹಾರ ವಿಧಾನಗಳು ಟೆಂಟಾಯ್ ಈ ಕೆಳಗಿನ ಹಂತಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಒಗಟುಗಳನ್ನು ಪರಿಹರಿಸಬಹುದು. ಒಂದು ಚುಕ್ಕೆ ಅಥವಾ ಚುಕ್ಕೆಯ ಒಂದು ಭಾಗವನ್ನು ಹೊಂದಿರುವ ಪಕ್ಕದ ಕೋಶಗಳ ನಡುವೆ ಗೋಡೆಗಳನ್ನು ಎಳೆಯಿರಿ. ಈ ಜೀವಕೋಶಗಳು ವಿವಿಧ ನಕ್ಷತ್ರಪುಂಜಗಳಿಗೆ ಸೇರಿರಬೇಕು. ತಿರುಗುವಿಕೆಯ ಸಮ್ಮಿತಿಯ ಪ್ರಕಾರ ಚುಕ್ಕೆಯ ಸುತ್ತ ಗೋಡೆಗಳನ್ನು ಎಳೆಯಿರಿ. ಗ್ರಿಡ್ನ ಗಡಿಗಳನ್ನು ಸಹ ಗೋಡೆಗಳೆಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ. ಒಂದು ಬಿಂದುವಿನಿಂದ 'ಸೆರೆಹಿಡಿಯಲಾದ' ಪ್ರದೇಶಗಳಲ್ಲಿ ಜೀವಕೋಶಗಳನ್ನು ಹುಡುಕಿ. ಇವು ಬೇರೆ ಯಾವುದೇ ಚುಕ್ಕೆಗಳಿಂದ ತಲುಪಲಾಗದ ಕೋಶಗಳಾಗಿವೆ. ಈ ಜೀವಕೋಶಗಳು ಆ ಚುಕ್ಕೆಗಾಗಿ ಮಾತ್ರ ನಕ್ಷತ್ರಪುಂಜಕ್ಕೆ ಸೇರಬಹುದು. ಒಗಟು ಪರಿಹಾರವಾಗುವವರೆಗೆ ಮೇಲಿನ ಹಂತಗಳನ್ನು ಪುನರಾವರ್ತಿಸಬಹುದು. ಹೆಚ್ಚು ಮುಂದುವರಿದ ಒಗಟುಗಳಲ್ಲಿ, ತಿರುಗುವಿಕೆಯ ಸಮ್ಮಿತಿಯ ಚಿತ್ರಣವನ್ನು ಪರಿಗಣಿಸುವುದು ಅಗತ್ಯವಾಗಬಹುದು. ಅದರ ತಿರುಗುವಿಕೆಯ ಸಮ್ಮಿತೀಯ ಕೋಶವನ್ನು ಪರಿಗಣಿಸುವಾಗ ಕೇವಲ ಒಂದು ಮಾನ್ಯ ಚುಕ್ಕೆಯನ್ನು ಹೊಂದಿರುವ ಕೋಶಗಳನ್ನು ಹುಡುಕಿ. ಒಂದು ಜೀವಕೋಶವು ಅದರ ಸಮ್ಮಿತೀಯ ಜೀವಕೋಶವು ಸಹ ಆ ನಕ್ಷತ್ರಪುಂಜಕ್ಕೆ ಸೇರಬಹುದಾದರೆ ಅದು ನಕ್ಷತ್ರಪುಂಜಕ್ಕೆ ಸೇರಬಹುದು. ಪಝಲ್ನ ಹೆಸರು, "ಟೆಂಟಾಯ್ ಶೋ", ಜಪಾನೀಸ್ನಲ್ಲಿ ಅರ್ಥೈಸಿಕೊಳ್ಳುವಾಗ ಎರಡು ಅರ್ಥಗಳನ್ನು ಹೊಂದಿದೆ. "ಹತ್ತು" ಎಂದರೆ ಡಾಟ್, ಆದರೆ "ತೈ ಶೋ" ಎಂದರೆ ಸಮ್ಮಿತಿ. ಖಗೋಳಶಾಸ್ತ್ರದ ವಸ್ತುಗಳನ್ನು ಉಲ್ಲೇಖಿಸಲು ಜಪಾನಿನ ಪದ "ಟೆಂಟಾಯ್" ಅನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಒಟ್ಟಾಗಿ, "ಟೆಂಟಾಯ್ ಶೋ" ಎಂದರೆ ತಿರುಗುವಿಕೆಯ ಸಮ್ಮಿತಿ ಮತ್ತು ಖಗೋಳಶಾಸ್ತ್ರದ ಪ್ರದರ್ಶನ ಎರಡೂ ಆಗಿರಬಹುದು. ಕಂಪ್ಯೂಟೇಶನಲ್ ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಎನ್. ಪಿ.-ಕಂಪ್ಲೀಟೆನೆಸ್ ಟೆಂಟಾಯ್ ಶೋ ಒಗಟು ಪರಿಹಾರವನ್ನು ಹೊಂದಿದೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವುದು ಎನ್. ಪಿ.-ಕಂಪ್ಲೀಟ್ ಎಂದು ತಿಳಿದುಬಂದಿದೆ. ಇದನ್ನು ಫ್ರೀಡ್ಮನ್ (2002) ಅವರು ಅನಿಯಂತ್ರಿತ ಬೂಲಿಯನ್ ಸರ್ಕ್ಯೂಟ್ಗಳಿಗೆ ಸಮಾನವಾದ ಒಗಟುಗಳನ್ನು ನಿರ್ಮಿಸುವ ಮೂಲಕ ಸಾಬೀತುಪಡಿಸಿದರು, ಇದು ಬೂಲಿಯನ್ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಯಿಂದಾಗಿ ಎನ್ಪಿ-ಪೂರ್ಣತೆಯನ್ನು ತೋರಿಸುತ್ತದೆ. ಎಲ್ಲಾ ನಕ್ಷತ್ರಪುಂಜಗಳು ಗರಿಷ್ಠ ಏಳು ಗಾತ್ರವನ್ನು ಹೊಂದಿರುವಾಗ ಒಗಟು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸುವ ಮೂಲಕ ಫೆರ್ಟಿನ್, ಜಮ್ಶಿಡಿ ಮತ್ತು ಕೊಮುಸಿವಿಕ್ಜ್ (2015) ಈ ಫಲಿತಾಂಶವನ್ನು ಬಲಪಡಿಸಿದರು. ಪುರಾವೆಯು ಒಗಟುಗಳನ್ನು ಪಾಸಿಟಿವ್ ಪ್ಲಾನರ್ 1-ಇನ್-3-ಎಸ್ಎಟಿಗೆ ಇಳಿಸುತ್ತದೆ, ಇದು ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಎಂದು ತಿಳಿದುಬಂದಿದೆ. ಡಿಮೈನ್, ಲೋಫ್ಲರ್ ಮತ್ತು ಷ್ಮಿಡ್ಟ್ (2021) ಎಲ್ಲಾ ನಕ್ಷತ್ರಪುಂಜಗಳು 1x1,1x3, ಅಥವಾ 3x1 ಗಾತ್ರದ ಆಯತಗಳಾಗಿ ಸೀಮಿತವಾಗಿದ್ದರೂ ಸಹ NP-ಸಂಪೂರ್ಣತೆಯನ್ನು ಸಾಬೀತುಪಡಿಸುವ ಮೂಲಕ ಇದನ್ನು ಮತ್ತಷ್ಟು ಬಲಪಡಿಸಿದರು. ನಿರ್ದಿಷ್ಟ ಆಕಾರವನ್ನು ನಿಖರವಾಗಿ ಆವರಿಸುವ ಕನಿಷ್ಠ ನಕ್ಷತ್ರಪುಂಜಗಳ ಗುಂಪನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿದೆ ಎಂದು ಅವರು ತೋರಿಸಿದರು. ಪರಿಹಾರ ಕ್ರಮಾವಳಿಗಳು ಟೆಂಟಾಯ್ ಶೋ ಒಗಟುಗಳನ್ನು ಗ್ರಿಡ್ನ ಎಲ್ಲಾ ಸಂಭವನೀಯ ಛೇದನಗಳ ಮೂಲಕ ಹೋಗಿ ಮತ್ತು ಅದು ಮಾನ್ಯ ಪರಿಹಾರವೇ ಎಂದು ಪರಿಶೀಲಿಸುವ ಮೂಲಕ ಘಾತೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಫೆರ್ಟಿನ್, ಜಮ್ಶಿದಿ ಮತ್ತು ಕೊಮುಸಿವಿಕ್ಜ್ (2015) ವಿವಿಧ ಪ್ರಕರಣಗಳಿಗೆ ಒಗಟುಗಳನ್ನು ಪರಿಹರಿಸಬಲ್ಲ ಬಹುಪದ-ಸಮಯದ ಕ್ರಮಾವಳಿಯನ್ನು ತೋರಿಸಿದರು, ಉದಾಹರಣೆಗೆಃ (ಎ) ಎಲ್ಲಾ ನಕ್ಷತ್ರಪುಂಜಗಳು ಗರಿಷ್ಠ ಎರಡು ಗಾತ್ರವನ್ನು ಹೊಂದಿರುವಾಗ, (ಬಿ) ಎಲ್ಲಾ ನಕ್ಷತ್ರಪುಂಜಗಳು ಚೌಕಗಳಾಗಿದ್ದಾಗ, ಮತ್ತು (ಸಿ) ಎಲ್ಲಾ ನಕ್ಷತ್ರಪುಂಜಗಳು ಕ್ಷುಲ್ಲಕವಾಗಿ ಸಂಪರ್ಕಗೊಂಡಾಗ. ನಿಕೋಲಿ ಒಗಟು ಪ್ರಕಾರಗಳ ಪಟ್ಟಿಯನ್ನು ಸಹ ನೋಡಿ ಉಲ್ಲೇಖಗಳು ತರ್ಕ ಒಗಟುಗಳು NP-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳು