FKT algorithm
ಮೈಕೆಲ್ ಫಿಶರ್, ಪೀಟರ್ ಕ್ಯಾಸ್ಟೆಲಿನ್ ಮತ್ತು ನೆವಿಲ್ಲೆ ಟೆಂಪರ್ಲಿ ಅವರ ಹೆಸರನ್ನು ಇಡಲಾದ ಫಿಶರ್-ಕ್ಯಾಸ್ಟೆಲಿನ್-ಟೆಂಪರ್ಲಿ (ಎಫ್ಕೆಟಿ) ಕ್ರಮಾವಳಿಯು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಸಮತಟ್ಟಾದ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸುತ್ತದೆ. ಸಾಮಾನ್ಯ ಗ್ರಾಫ್ಗಳಿಗೆ ಇದೇ ಕಾರ್ಯವು #P-ಪೂರ್ಣವಾಗಿದೆ. ಪರಿಪೂರ್ಣವಾಗಿರಬೇಕಾದ ಅಗತ್ಯವಿಲ್ಲದ ಹೊಂದಾಣಿಕೆಗಳಿಗೆ, ಅವುಗಳನ್ನು ಎಣಿಸುವುದು ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಿಗೂ ಸಹ #P-ಪೂರ್ಣವಾಗಿರುತ್ತದೆ. ಎಫ್ಕೆಟಿ ಅಲ್ಗಾರಿದಮ್ನ ಪ್ರಮುಖ ಉದ್ದೇಶವೆಂದರೆ ಸಮಸ್ಯೆಯನ್ನು ಗ್ರಾಫ್ನ ಪ್ಲ್ಯಾನರ್ ಎಂಬೆಡಿಂಗಿನಿಂದ ಪಡೆದ ಸ್ಕ್ಯೂ-ಸಿಮೆಟ್ರಿಕ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಪ್ಫಾಫಿಯನ್ ಗಣನೆಯಾಗಿ ಪರಿವರ್ತಿಸುವುದು. ಈ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಫಾಫಿಯನ್ ಅನ್ನು ನಂತರ ಪ್ರಮಾಣಿತ ನಿರ್ಣಾಯಕ ಕ್ರಮಾವಳಿಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಲೆಕ್ಕಹಾಕಲಾಗುತ್ತದೆ. ಪ್ಲ್ಯಾನರ್ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಗಳನ್ನು ಎಣಿಸುವ ಸಮಸ್ಯೆಯು ಸಂಖ್ಯಾಶಾಸ್ತ್ರೀಯ ಯಂತ್ರಶಾಸ್ತ್ರ ಮತ್ತು ರಸಾಯನಶಾಸ್ತ್ರದಲ್ಲಿ ತನ್ನ ಬೇರುಗಳನ್ನು ಹೊಂದಿದೆ, ಅಲ್ಲಿ ಮೂಲ ಪ್ರಶ್ನೆಯೆಂದರೆಃ ಡಯಾಟಾಮಿಕ್ ಅಣುಗಳನ್ನು ಮೇಲ್ಮೈಯಲ್ಲಿ ಹೀರಿಕೊಂಡರೆ, ಒಂದೇ ಪದರವನ್ನು ರಚಿಸಿದರೆ, ಅವುಗಳನ್ನು ಎಷ್ಟು ರೀತಿಯಲ್ಲಿ ಜೋಡಿಸಬಹುದು? ವಿಭಜನೆಯ ಕಾರ್ಯವು ಸಮತೋಲನದಲ್ಲಿರುವ ವ್ಯವಸ್ಥೆಯ ಸಂಖ್ಯಾಶಾಸ್ತ್ರೀಯ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಸಂಕೇತಿಸುವ ಒಂದು ಪ್ರಮುಖ ಪ್ರಮಾಣವಾಗಿದೆ ಮತ್ತು ಹಿಂದಿನ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸಲು ಇದನ್ನು ಬಳಸಬಹುದು. ಆದಾಗ್ಯೂ, ವಿಭಜನೆಯ ಕಾರ್ಯವನ್ನು ಅದರ ವ್ಯಾಖ್ಯಾನದಿಂದ ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಪ್ರಯತ್ನಿಸುವುದು ಪ್ರಾಯೋಗಿಕವಲ್ಲ. ಹೀಗಾಗಿ ಭೌತಿಕ ವ್ಯವಸ್ಥೆಯನ್ನು ನಿಖರವಾಗಿ ಪರಿಹರಿಸಲು ನಿಖರವಾಗಿ ಲೆಕ್ಕ ಹಾಕಲು ಸಾಕಷ್ಟು ಸರಳವಾದ ನಿರ್ದಿಷ್ಟ ಭೌತಿಕ ವ್ಯವಸ್ಥೆಗೆ ವಿಭಜನಾ ಕಾರ್ಯದ ಪರ್ಯಾಯ ರೂಪವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು. 1960ರ ದಶಕದ ಆರಂಭದಲ್ಲಿ, ನಿಖರವಾಗಿ ಪರಿಹರಿಸಬಹುದಾದ ವ್ಯಾಖ್ಯಾನವು ಕಠಿಣವಾಗಿರಲಿಲ್ಲ. ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನವು ಬಹುಪದ ಸಮಯದ ಪರಿಚಯದೊಂದಿಗೆ ಕಠಿಣವಾದ ವ್ಯಾಖ್ಯಾನವನ್ನು ಒದಗಿಸಿದೆ, ಇದು 1965ರ ಕಾಲದ್ದಾಗಿದೆ. ಅಂತೆಯೇ, ಈ ರೀತಿಯ ಎಣಿಕೆಯ ಸಮಸ್ಯೆಗೆ ನಿಖರವಾಗಿ ಪರಿಹರಿಸಲಾಗುವುದಿಲ್ಲ ಎಂಬ ಸಂಕೇತವು 1979 ರಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ #P-ಗಡಸುತನಕ್ಕೆ ಅನುಗುಣವಾಗಿರಬೇಕು. ಪರಿಗಣಿಸಬೇಕಾದ ಮತ್ತೊಂದು ರೀತಿಯ ಭೌತಿಕ ವ್ಯವಸ್ಥೆಯು ಡೈಮರ್ಗಳಿಂದ ಕೂಡಿದೆ, ಇದು ಎರಡು ಪರಮಾಣುಗಳನ್ನು ಹೊಂದಿರುವ ಪಾಲಿಮರ್ ಆಗಿದೆ. ಡೈಮರ್ ಮಾದರಿಯು ಗ್ರಾಫ್ನ ಡೈಮರ್ ಹೊದಿಕೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸುತ್ತದೆ. ಪರಿಗಣಿಸಬೇಕಾದ ಮತ್ತೊಂದು ಭೌತಿಕ ವ್ಯವಸ್ಥೆಯು ಮಂಜುಗಡ್ಡೆಯ ರೂಪದಲ್ಲಿ H2O ಅಣುಗಳ ಬಂಧವಾಗಿದೆ. ಇದನ್ನು ನಿರ್ದೇಶಿತ, 3-ನಿಯಮಿತ ರೇಖಾಚಿತ್ರವಾಗಿ ರೂಪಿಸಬಹುದು, ಅಲ್ಲಿ ಪ್ರತಿ ಶೃಂಗದ ಅಂಚುಗಳ ದೃಷ್ಟಿಕೋನವು ಒಂದೇ ಆಗಿರಬಾರದು. ಈ ಮಾದರಿಯು ಎಷ್ಟು ಅಂಚಿನ ದೃಷ್ಟಿಕೋನಗಳನ್ನು ಹೊಂದಿದೆ? ಡೈಮರ್ಗಳನ್ನು ಒಳಗೊಂಡ ಭೌತಿಕ ವ್ಯವಸ್ಥೆಗಳಿಂದ ಪ್ರೇರೇಪಿಸಲ್ಪಟ್ಟ, 1961ರಲ್ಲಿ, ಪೀಟರ್ ಕ್ಯಾಸ್ಟೆಲಿನ್ ಮತ್ತು ನೆವಿಲ್ಲೆ ಟೆಂಪರ್ಲಿ ಮತ್ತು ಮೈಕೆಲ್ ಫಿಶರ್ ಸ್ವತಂತ್ರವಾಗಿ m-by-n ಆಯತಕ್ಕೆ ಡೊಮಿನೊ ಟಿಲಿಂಗ್ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಕೊಂಡರು. ಇದು m-by-n ಜಾಲರಿ ನಕ್ಷೆಗಾಗಿ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸುವುದಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. 1967ರ ಹೊತ್ತಿಗೆ, ಕ್ಯಾಸ್ಟೆಲಿನ್ ಈ ಫಲಿತಾಂಶವನ್ನು ಎಲ್ಲಾ ಸಮತಟ್ಟಾದ ನಕ್ಷೆಗಳಿಗೆ ಸಾಮಾನ್ಯೀಕರಿಸಿದ್ದರು. ಅಲ್ಗಾರಿದಮ್ ವಿವರಣೆ ಮುಖ್ಯ ಒಳನೋಟವೆಂದರೆ ಗ್ರಾಫ್ ಜಿ ಯ ಸಮೀಪದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಪ್ಫಾಫಿಯಾನ್ನಲ್ಲಿನ ಪ್ರತಿ ಶೂನ್ಯವಲ್ಲದ ಪದವು ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಗೆ ಅನುರೂಪವಾಗಿದೆ. ಹೀಗಾಗಿ, ಪಫಾಫಿಯಾನ್ನಲ್ಲಿನ ಪದಗಳ ಎಲ್ಲಾ ಚಿಹ್ನೆಗಳನ್ನು ಜೋಡಿಸಲು ಜಿ ಯ ದೃಷ್ಟಿಕೋನವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಾದರೆ (ಯಾವುದೇ ವಿಷಯ + ಅಥವಾ-ಅಲ್ಲ), ಆಗ ಪಫಾಫಿಯಾನ್ನ ಸಂಪೂರ್ಣ ಮೌಲ್ಯವು ಜಿ ಯಲ್ಲಿನ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಗಳ ಸಂಖ್ಯೆಯಾಗಿರುತ್ತದೆ. ಎಫ್. ಕೆ. ಟಿ ಅಲ್ಗಾರಿದಮ್ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ ಜಿಗಾಗಿ ಅಂತಹ ಕಾರ್ಯವನ್ನು ಮಾಡುತ್ತದೆ. ಅದು ಕಂಡುಕೊಳ್ಳುವ ದೃಷ್ಟಿಕೋನವನ್ನು ಪಫಾಫಿಯನ್ ದೃಷ್ಟಿಕೋನ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. G = (V, E) ಪಕ್ಕದಲ್ಲಿರುವ ಮ್ಯಾಟ್ರಿಕ್ಸ್ A ಯೊಂದಿಗೆ ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ ಆಗಿರಲಿ. ಪಿಎಂ (ಎನ್) ಅನ್ನು ಜೋಡಿಗಳಾಗಿ n ಅಂಶಗಳ ವಿಭಾಗಗಳ ಗುಂಪಾಗಿ ವ್ಯಾಖ್ಯಾನಿಸಿ, ನಂತರ ಜಿ ನಲ್ಲಿನ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಗಳ ಸಂಖ್ಯೆಯು ಇದಕ್ಕೆ ನಿಕಟವಾಗಿ ಸಂಬಂಧಿಸಿದೆ, ಇದು ಎನ್ ಬೈ ಎನ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಎ ಗೆ ಫಾಫಿಯನ್ ಆಗಿದೆ, ಅಲ್ಲಿ ಎಸ್ಜಿಎನ್ (ಎಂ) ಕ್ರಮಪಲ್ಲಟನೆಯ ಸಂಕೇತವಾಗಿದೆ ಎಂ. ಜಿ ಯ ಎ ಫಾಫಿಯನ್ ದೃಷ್ಟಿಕೋನವು ಪಕ್ಕದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಬಿ ಯೊಂದಿಗೆ ನಿರ್ದೇಶಿಸಿದ ಗ್ರಾಫ್ ಎಚ್ ಆಗಿದೆ, ಅಂದರೆ ಪಿಎಫ್ (ಬಿ) = ಪರ್ಫ್ಮ್ಯಾಚ್ (ಜಿ). ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು ಸಮರ್ಥವಾಗಿ ಗಣಿಸಬಹುದಾದ ಪ್ಫಾಫಿಯನ್ ದೃಷ್ಟಿಕೋನವನ್ನು ಹೊಂದಿವೆ ಎಂದು 1967ರಲ್ಲಿ ಕ್ಯಾಸ್ಟೆಲಿನ್ ಸಾಬೀತುಪಡಿಸಿದರು. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಸಮತಲ ನಕ್ಷೆ G ಗೆ, H ಎಂಬುದು G ಯ ನಿರ್ದೇಶಿತ ಆವೃತ್ತಿಯಾಗಿರಲಿ, ಅಲ್ಲಿ G ಯ ಸಮತಟ್ಟಾದ ಒಳಸೇರಿಸುವಿಕೆಯಲ್ಲಿ ಪ್ರತಿ ಮುಖಕ್ಕೂ ಬೆಸ ಸಂಖ್ಯೆಯ ಅಂಚುಗಳು ಪ್ರದಕ್ಷಿಣಾಕಾರವಾಗಿ ಆಧಾರಿತವಾಗಿರುತ್ತವೆ. ನಂತರ H ಎಂಬುದು G ಯ ಫಾಫಿಯನ್ ದೃಷ್ಟಿಕೋನವಾಗಿದೆ. ಅಂತಿಮವಾಗಿ, ಯಾವುದೇ ವಕ್ರ-ಸಮಮಿತಿಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ A ಗೆ, ಅಲ್ಲಿ ಡಿಟ್ (A) A ಯ ನಿರ್ಣಾಯಕವಾಗಿದೆ. ಈ ಫಲಿತಾಂಶವು ಆರ್ಥರ್ ಕೇಲಿಯ ಕಾರಣದಿಂದಾಗಿದೆ. ನಿರ್ಣಾಯಕಗಳು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಗಣಿಸಬಹುದಾದ ಕಾರಣ, ಪರ್ಫ್ಮ್ಯಾಚ್ (ಜಿ) ಕೂಡ. ಉನ್ನತ ಮಟ್ಟದ ವಿವರಣೆ ಜಿ ಯ ಪ್ಲ್ಯಾನರ್ ಎಂಬೆಡಿಂಗ್ ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ. ಇನ್ಪುಟ್ ಗ್ರಾಫ್ನ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಟಿ 1 ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ ಜಿ. ಜಿ ಯಲ್ಲಿನ ಪ್ರತಿ ಅಂಚಿಗೆ ಅನಿಯಂತ್ರಿತ ದೃಷ್ಟಿಕೋನವನ್ನು ನೀಡಿ ಅದು ಟಿ 1 ನಲ್ಲಿದೆ. ಪ್ಲ್ಯಾನರ್ ಎಂಬೆಡಿಂಗ್ ಅನ್ನು ಬಳಸಿ G ಯ ಡ್ಯುಯಲ್ ಗ್ರಾಫ್ನಂತೆಯೇ ಅದೇ ಶೃಂಗದ ಸೆಟ್ ಹೊಂದಿರುವ (ನಿರ್ದೇಶಿಸದ) ಗ್ರಾಫ್ T2 ಅನ್ನು ರಚಿಸಿ. G ಯಲ್ಲಿನ ಅವುಗಳ ಅನುಗುಣವಾದ ಮುಖಗಳು T1 ನಲ್ಲಿಲ್ಲದ G ಯಲ್ಲಿ ಒಂದು ಅಂಚನ್ನು ಹಂಚಿಕೊಂಡರೆ ಎರಡು ಶೃಂಗಗಳ ನಡುವೆ T2 ನಲ್ಲಿ ಒಂದು ಅಂಚನ್ನು ರಚಿಸಿ. (ಟಿ2 ಒಂದು ಮರವಾಗಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ.) T2 ನಲ್ಲಿರುವ ಪ್ರತಿ ಎಲೆ v ಗೆ (ಅದು ಮೂಲವೂ ಅಲ್ಲ): e ಎಂಬುದು ಇನ್ನೂ ದೃಷ್ಟಿಕೋನವನ್ನು ಹೊಂದಿರದ v ಗೆ ಅನುಗುಣವಾದ ಮುಖದಲ್ಲಿರುವ G ಯ ಏಕೈಕ ತುದಿಯಾಗಿರಲಿ. ಗಡಿಯಾರದ ದಿಕ್ಕಿನಲ್ಲಿರುವ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ಬೆಸವಾಗುವಂತೆ e ಗೆ ಒಂದು ದೃಷ್ಟಿಕೋನವನ್ನು ನೀಡಿ. T2 ನಿಂದ v ಅನ್ನು ತೆಗೆದುಹಾಕಿ. G ನ ಅಡ್ಜಸೆನ್ಸಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಪ್ಫಾಫಿಯಾನ್ನ ಸಂಪೂರ್ಣ ಮೌಲ್ಯವನ್ನು ಹಿಂತಿರುಗಿಸಿ, ಇದು ನಿರ್ಣಾಯಕದ ವರ್ಗಮೂಲವಾಗಿದೆ. ಸಾಮಾನ್ಯೀಕರಣಗಳು ಕೊನೆಯ ಹಂತದಲ್ಲಿ ಅಡ್ಜಸೆನ್ಸಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಾಗಿ ಟುಟ್ಟೆ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಬಳಸುವ ಮೂಲಕ ತೂಕದ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಗಳ ಮೊತ್ತವನ್ನು ಸಹ ಲೆಕ್ಕ ಹಾಕಬಹುದು. ಕುರಟೋವ್ಸ್ಕಿಯ ಪ್ರಮೇಯವು, ಒಂದು ಸೀಮಿತ ರೇಖಾಚಿತ್ರವು ಕೆ5 (ಐದು ಶೃಂಗಗಳ ಮೇಲೆ ಸಂಪೂರ್ಣ ರೇಖಾಚಿತ್ರ) ಅಥವಾ ಕೆ3,3 (ಗಾತ್ರ ಮೂರರ ಎರಡು ವಿಭಾಗಗಳ ಮೇಲೆ ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ರೇಖಾಚಿತ್ರ) ಗೆ ಯಾವುದೇ ಹೋಮಿಯೊಮಾರ್ಫಿಕ್ ಉಪ ರೇಖಾಚಿತ್ರವನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ ಮಾತ್ರ ಸಮತಟ್ಟಾಗಿರುತ್ತದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ವಿಜಯ್ ವಜೀರಾನಿ ಅವರು ಎಫ್ಕೆಟಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕೆ3,3 ಗೆ ಸಬ್ಗ್ರಾಫ್ ಹೋಮಿಯೊಮಾರ್ಫಿಕ್ ಅನ್ನು ಹೊಂದಿರದ ಗ್ರಾಫ್ಗಳಿಗೆ ಸಾಮಾನ್ಯೀಕರಿಸಿದರು. ಸಾಮಾನ್ಯ ಗ್ರಾಫ್ನಲ್ಲಿ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸುವುದು #P-ಕಂಪ್ಲೀಟ್ ಆಗಿರುವುದರಿಂದ, P ಯ ಕಾರ್ಯ ಆವೃತ್ತಿಯಾದ FP, #P ಗೆ ಸಮನಾಗಿಲ್ಲದಿದ್ದರೆ ಇನ್ಪುಟ್ ಗ್ರಾಫ್ನಲ್ಲಿ ಕೆಲವು ನಿರ್ಬಂಧಗಳು ಬೇಕಾಗುತ್ತವೆ. ಹೋಸೋಯಾ ಸೂಚ್ಯಂಕ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಎಣಿಕೆ ಹೊಂದಾಣಿಕೆಗಳು, ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಿಗೂ ಸಹ #P-ಕಂಪ್ಲೀಟ್ ಆಗಿರುತ್ತವೆ. ಅಪ್ಲಿಕೇಶನ್ಗಳು ಎಫ್. ಕೆ. ಟಿ ಅಲ್ಗಾರಿದಮ್ ಹೋಲೋಗ್ರಾಫಿಕ್ ಅಲ್ಗಾರಿದಮ್ಗಳಲ್ಲಿ ಮ್ಯಾಚ್ಗೇಟ್ಗಳ ಮೂಲಕ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ವ್ಯಾಪಕವಾದ ಬಳಕೆಯನ್ನು ಕಂಡಿದೆ. ಉದಾಹರಣೆಗೆ, ಮೇಲೆ ತಿಳಿಸಲಾದ ಐಸ್ ಮಾದರಿಯ ಸಮತಟ್ಟಾದ ಆವೃತ್ತಿಯನ್ನು ಪರಿಗಣಿಸಿ, ಇದು ತಾಂತ್ರಿಕ ಹೆಸರು #PL-3-NAE-SAT ಅನ್ನು ಹೊಂದಿದೆ (ಇಲ್ಲಿ NAE ಎಂದರೆ "ಎಲ್ಲಾ ಸಮಾನವಲ್ಲ"). ಈ ಸಮಸ್ಯೆಗೆ ಮ್ಯಾಚ್ಗೇಟ್ಗಳನ್ನು ಬಳಸುವ ಬಹುಪದ ಸಮಯದ ಕ್ರಮಾವಳಿಯನ್ನು ವೇಲಿಯಂಟ್ ಕಂಡುಹಿಡಿದಿದೆ. ಹೆಚ್ಚಿನ ಇತಿಹಾಸ, ಮಾಹಿತಿ ಮತ್ತು ಉದಾಹರಣೆಗಳನ್ನು ಡಿಮಿಟ್ರಿ ಕಮೆನೆಟ್ಸ್ಕಿಯ ಪಿಎಚ್ಡಿ ಪ್ರಬಂಧದ 2ನೇ ಅಧ್ಯಾಯ ಮತ್ತು 5.3.2ನೇ ವಿಭಾಗದಲ್ಲಿ ಕಾಣಬಹುದು.