Generalized geography
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಸಾಮಾನ್ಯೀಕೃತ ಭೌಗೋಳಿಕತೆಯು ಪ್ರಸಿದ್ಧವಾದ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಭೌಗೋಳಿಕತೆಯು ಮಕ್ಕಳ ಆಟವಾಗಿದ್ದು, ಅಲ್ಲಿ ಆಟಗಾರರು ವಿಶ್ವದ ಎಲ್ಲೆಡೆಯಿಂದ ನಗರಗಳಿಗೆ ಹೆಸರಿಡುತ್ತಾರೆ. ಆಯ್ಕೆ ಮಾಡಲಾದ ಪ್ರತಿಯೊಂದು ನಗರವು ಹಿಂದಿನ ನಗರದ ಹೆಸರನ್ನು ಕೊನೆಗೊಳಿಸಿದ ಅದೇ ಅಕ್ಷರದಿಂದ ಪ್ರಾರಂಭವಾಗಬೇಕು. ಪುನರಾವರ್ತನೆ ಅನುಮತಿಸಲಾಗುವುದಿಲ್ಲ. ಆಟವು ಅನಿಯಂತ್ರಿತ ಆರಂಭದ ನಗರದಿಂದ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ ಮತ್ತು ಅವನು ಅಥವಾ ಅವಳು ಮುಂದುವರಿಯಲು ಸಾಧ್ಯವಾಗದ ಕಾರಣ ಆಟಗಾರನು ಸೋತಾಗ ಕೊನೆಗೊಳ್ಳುತ್ತದೆ. ಗ್ರಾಫ್ ಮಾದರಿ ಆಟವನ್ನು ದೃಶ್ಯೀಕರಿಸಲು, ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಅನ್ನು ನಿರ್ಮಿಸಬಹುದು, ಅದರ ನೋಡ್ಗಳು ವಿಶ್ವದ ಪ್ರತಿಯೊಂದು ನಗರಗಳಾಗಿವೆ. ಸಿಟಿ ಲೇಬಲಿಂಗ್ N2, ಸಿಟಿ ಲೇಬಲಿಂಗ್ ನೋಡ್ N1 ಹೆಸರನ್ನು ಕೊನೆಗೊಳಿಸುವ ಅಕ್ಷರದೊಂದಿಗೆ ಪ್ರಾರಂಭವಾದರೆ ಮಾತ್ರ ನೋಡ್ N1 ನಿಂದ ನೋಡ್ N2 ಗೆ ಬಾಣವನ್ನು ಸೇರಿಸಲಾಗುತ್ತದೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಆಟದ ನಿಯಮಗಳ ಪ್ರಕಾರ ಮೊದಲನೆಯದು ಎರಡನೆಯದಕ್ಕೆ ಕಾರಣವಾಗಬಹುದಾದರೆ ನಾವು ಒಂದು ನಗರದಿಂದ ಇನ್ನೊಂದು ನಗರಕ್ಕೆ ಬಾಣವನ್ನು ಎಳೆಯುತ್ತೇವೆ. ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ನಲ್ಲಿನ ಪ್ರತಿ ಪರ್ಯಾಯ ಅಂಚು ಪ್ರತಿ ಆಟಗಾರನಿಗೆ ಅನುರೂಪವಾಗಿದೆ (ಇಬ್ಬರು ಆಟಗಾರರ ಆಟಕ್ಕೆ). ಮಾರ್ಗವನ್ನು ವಿಸ್ತರಿಸಲು ಸಾಧ್ಯವಾಗದ ಮೊದಲ ಆಟಗಾರನು ಸೋಲುತ್ತಾನೆ. ಆಟದ ಒಂದು ವಿವರಣೆಯನ್ನು (ಮಿಚಿಗನ್ನ ಕೆಲವು ನಗರಗಳನ್ನು ಒಳಗೊಂಡಿರುವ) ಕೆಳಗಿನ ಚಿತ್ರದಲ್ಲಿ ತೋರಿಸಲಾಗಿದೆ. ಸಾಮಾನ್ಯೀಕೃತ ಭೌಗೋಳಿಕ (ಜಿಜಿ) ಆಟದಲ್ಲಿ, ನಾವು ನಗರದ ಹೆಸರುಗಳ ಗ್ರಾಫ್ ಅನ್ನು ಅನಿಯಂತ್ರಿತ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ನಿಂದ ಬದಲಾಯಿಸುತ್ತೇವೆ. ಈ ಕೆಳಗಿನ ರೇಖಾಚಿತ್ರವು ಸಾಮಾನ್ಯೀಕೃತ ಭೌಗೋಳಿಕ ಆಟದ ಒಂದು ಉದಾಹರಣೆಯಾಗಿದೆ. ಆಟವನ್ನು ಆಡುವುದು ನಾವು ಪಿ 1 ಅನ್ನು ಮೊದಲು ಚಲಿಸುವ ಆಟಗಾರ ಮತ್ತು ಪಿ 2 ಅನ್ನು ಎರಡನೇ ಚಲಿಸುವ ಆಟಗಾರ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತೇವೆ ಮತ್ತು ನೋಡ್ಗಳನ್ನು ಎನ್ 1 ಗೆ ಎನ್ ಎನ್ ಎಂದು ಹೆಸರಿಸುತ್ತೇವೆ. ಮೇಲಿನ ಚಿತ್ರದಲ್ಲಿ, ಪಿ1 ಈ ಕೆಳಗಿನಂತೆ ಗೆಲುವಿನ ಕಾರ್ಯತಂತ್ರವನ್ನು ಹೊಂದಿದೆಃ ಎನ್1 ಅಂಕಗಳು ನೋಡ್ಗಳಾದ ಎನ್2 ಮತ್ತು ಎನ್3ಗಳಿಗೆ ಮಾತ್ರ. ಹೀಗಾಗಿ ಪಿ1ನ ಮೊದಲ ಚಲನೆ ಈ ಎರಡು ಆಯ್ಕೆಗಳಲ್ಲಿ ಒಂದಾಗಿರಬೇಕು. ಪಿ1 ಎನ್2 ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ (ಪಿ1 ಎನ್3 ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಿದರೆ, ಪಿ2 ಎನ್9 ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ ಏಕೆಂದರೆ ಅದು ಏಕೈಕ ಆಯ್ಕೆಯಾಗಿದೆ ಮತ್ತು ಪಿ1 ಕಳೆದುಕೊಳ್ಳುತ್ತದೆ). ಮುಂದಿನ ಪಿ2 ಎನ್4 ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ ಏಕೆಂದರೆ ಇದು ಉಳಿದಿರುವ ಏಕೈಕ ಆಯ್ಕೆಯಾಗಿದೆ. ಪಿ1 ಈಗ ಎನ್5 ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ ಮತ್ತು ಪಿ2 ತರುವಾಯ ಎನ್3 ಅಥವಾ ಎನ್7 ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ಪಿ2 ನ ಆಯ್ಕೆಯ ಹೊರತಾಗಿಯೂ, ಪಿ1 ಎನ್9 ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ ಮತ್ತು ಪಿ2 ಗೆ ಯಾವುದೇ ಉಳಿದ ಆಯ್ಕೆಗಳಿಲ್ಲ ಮತ್ತು ಆಟವನ್ನು ಕಳೆದುಕೊಳ್ಳುತ್ತದೆ. ಸಾಮಾನ್ಯೀಕೃತ ಭೌಗೋಳಿಕ ಆಟದಲ್ಲಿ ಯಾವ ಆಟಗಾರನು ಗೆಲ್ಲುವ ತಂತ್ರವನ್ನು ಹೊಂದಿದ್ದಾನೆ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವ ಸಮಸ್ಯೆಯು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ. ಸಾಮಾನ್ಯೀಕೃತ ಭೌಗೋಳಿಕತೆಯು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಯಲ್ಲಿದೆ. ನೋಡ್ ಬಿ. ಯಿಂದ ಪ್ರಾರಂಭವಾಗುವ ಗ್ರಾಫ್ ಜಿ. ಯಲ್ಲಿ ಆಡುವ ಸಾಮಾನ್ಯೀಕೃತ ಭೌಗೋಳಿಕ ಆಟಕ್ಕೆ ಜಿ. ಜಿ. = {75ಜಿ, ಬಿ. ಪಿ. ಎಲ್. ಎ. | ಪಿ1 ಗೆಲುವಿನ ಕಾರ್ಯತಂತ್ರವನ್ನು ಹೊಂದಿದೆ; ಜಿ. ಜಿ. bul. ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ಅನ್ನು ತೋರಿಸಲು, ಯಾವ ಆಟಗಾರನು ಗೆಲ್ಲುವ ಕಾರ್ಯತಂತ್ರವನ್ನು ಹೊಂದಿದ್ದಾನೆ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವ ಬಹುಪದೀಯ-ಸ್ಥಳ ಪುನರಾವರ್ತಿತ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನಾವು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತೇವೆ. ಜಿ. ಜಿ. ಯ ಒಂದು ಉದಾಹರಣೆಯನ್ನು ಗಮನಿಸಿದರೆ, ಅಲ್ಲಿ ಜಿ ಒಂದು ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಆಗಿದೆ ಮತ್ತು ಎನ್ಸ್ಟಾರ್ಟ್ ಗೊತ್ತುಪಡಿಸಿದ ಪ್ರಾರಂಭ ನೋಡ್ ಆಗಿದೆ, ಅಲ್ಗಾರಿದಮ್ ಎಂ ಈ ಕೆಳಗಿನಂತೆ ಮುಂದುವರಿಯುತ್ತದೆಃ ಎಂ (ಎಸ್ಟಿಜಿ, ಎನ್ಸ್ಟಾರ್ಟ್ ಎಲ್ಓ): ನೋಡ್ ಎನ್ಸ್ಟಾರ್ಟ್ನ ಹೊರ-ಮಟ್ಟವನ್ನು ಅಳೆಯಿರಿ. ಈ ಡಿಗ್ರಿ 0 ಆಗಿದ್ದರೆ, ಹಿಂತಿರುಗಿ, ಏಕೆಂದರೆ ಆಟಗಾರನಿಗೆ ಯಾವುದೇ ಚಲನೆಗಳು ಲಭ್ಯವಿಲ್ಲ. ಒಂದು ತುದಿಯಿಂದ nstart ನಿಂದ ತಲುಪಬಹುದಾದ ಎಲ್ಲಾ ನೋಡ್ಗಳ ಪಟ್ಟಿಯನ್ನು ರಚಿಸಿಃ n1, n2,., ni. ಜಿ1 ಅನ್ನು ರೂಪಿಸಲು ಜಿ ಯಿಂದ ಎನ್ಸ್ಟಾರ್ಟ್ ಮತ್ತು ಅದಕ್ಕೆ ಜೋಡಿಸಲಾದ ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ತೆಗೆದುಹಾಕಿ. n1,., ni ಪಟ್ಟಿಯಲ್ಲಿರುವ ಪ್ರತಿ ನೋಡ್ nj ಗೆ, M (75G1, nj ಆಹಾತ) ಎಂದು ಕರೆ ಮಾಡಿ. ಈ ಎಲ್ಲಾ ಕರೆಗಳು ಹಿಂತಿರುಗಿ ಸ್ವೀಕರಿಸಿದರೆ, ಪಿ1 ಯಾವ ನಿರ್ಧಾರವನ್ನು ತೆಗೆದುಕೊಂಡರೂ, ಪಿ2 ಗೆಲ್ಲುವ ತಂತ್ರವನ್ನು ಹೊಂದಿದೆ, ಆದ್ದರಿಂದ ಹಿಂತಿರುಗಿ ತಿರಸ್ಕರಿಸಿ. ಇಲ್ಲದಿದ್ದರೆ (ಒಂದು ಕರೆ ಹಿಂತಿರುಗಿದರೆ ತಿರಸ್ಕರಿಸಿದರೆ) ಪಿ1ಗೆ ಪಿ2ಗಾಗಿ ಯಾವುದೇ ಯಶಸ್ವಿ ತಂತ್ರಗಳನ್ನು ನಿರಾಕರಿಸುವ ಆಯ್ಕೆ ಇರುತ್ತದೆ, ಆದ್ದರಿಂದ ಹಿಂತಿರುಗಿ ಸ್ವೀಕರಿಸಿ. ಅಲ್ಗಾರಿದಮ್ ಎಂ ಸ್ಪಷ್ಟವಾಗಿ ಜಿಜಿಯನ್ನು ನಿರ್ಧರಿಸುತ್ತದೆ. ಇದು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ನಲ್ಲಿದೆ ಏಕೆಂದರೆ ಬಳಸಿದ ಏಕೈಕ ಸ್ಪಷ್ಟವಲ್ಲದ ಬಹುಪದೀಯ ಕಾರ್ಯಕ್ಷೇತ್ರವು ರಿಕರ್ಶನ್ ಸ್ಟಾಕ್ನಲ್ಲಿದೆ. ರಿಕರ್ಶನ್ ಸ್ಟ್ಯಾಕ್ ಬಳಸುವ ಜಾಗವು ಬಹುಪದಿಯಾಗಿದೆ ಏಕೆಂದರೆ ಪ್ರತಿ ಹಂತದ ರಿಕರ್ಶನ್ ಸ್ಟ್ಯಾಕ್ಗೆ ಒಂದೇ ನೋಡ್ ಅನ್ನು ಸೇರಿಸುತ್ತದೆ ಮತ್ತು ಹೆಚ್ಚಿನ n ಹಂತಗಳಿವೆ, ಅಲ್ಲಿ n ಎಂಬುದು Gಯಲ್ಲಿನ ನೋಡ್ಗಳ ಸಂಖ್ಯೆ. ಇದು ಮೂಲಭೂತವಾಗಿ ಡೆಪ್ತ್-ಫಸ್ಟ್ ಸರ್ಚ್ಗೆ ಸಮನಾಗಿರುತ್ತದೆ. ಈ ಕೆಳಗಿನ ಪುರಾವೆಯು ಡೇವಿಡ್ ಲಿಚ್ಟೆನ್ಸ್ಟೈನ್ ಮತ್ತು ಮೈಕೆಲ್ ಸಿಪ್ಸರ್ ಅವರ ಕಾರಣದಿಂದಾಗಿದೆ. ಜಿಜಿಯ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ.-ಗಡಸುತನವನ್ನು ಸ್ಥಾಪಿಸಲು, ನಾವು ಬಹುಪದ ಸಮಯದಲ್ಲಿ (ಪಿ) ಜಿ. ಜಿ. ಗೆ ಫಾರ್ಮುಲಾ-ಗೇಮ್ ಸಮಸ್ಯೆಯನ್ನು (ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ.-ಹಾರ್ಡ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ) ಕಡಿಮೆ ಮಾಡಬಹುದು. ಸಂಕ್ಷಿಪ್ತವಾಗಿ ಹೇಳುವುದಾದರೆ, ಫಾರ್ಮುಲಾ-ಗೇಮ್ ಸಮಸ್ಯೆಯ ಒಂದು ಉದಾಹರಣೆಯು ಕ್ವಾಂಟಿಫೈಡ್ ಬೂಲಿಯನ್ ಸೂತ್ರವನ್ನು φ = HEx1 βx2 HEx3. Qxk (si) ಅನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಅಲ್ಲಿ Q ಎಂಬುದು HE ಅಥವಾ β ಆಗಿರುತ್ತದೆ. ಈ ಆಟವನ್ನು ಪಾ ಮತ್ತು ಪೆ ಎಂಬ ಇಬ್ಬರು ಆಟಗಾರರು ಆಡುತ್ತಾರೆ, ಅವರು ಅನುಕ್ರಮ xi ಗೆ ಪರ್ಯಾಯವಾಗಿ ಮೌಲ್ಯಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತಾರೆ. ಸೂತ್ರವು ನಿಜವಾಗಿದ್ದರೆ ಪೆ ಆಟವನ್ನು ಗೆಲ್ಲುತ್ತಾನೆ, ಮತ್ತು ಸೂತ್ರವು ತಪ್ಪಾಗಿದ್ದರೆ ಪಾ ಗೆಲ್ಲುತ್ತಾನೆ. ಸೂತ್ರವು ಕಾಂಜಂಕ್ಟಿವ್ ನಾರ್ಮಲ್ ರೂಪದಲ್ಲಿದೆ ಎಂದು ಭಾವಿಸಲಾಗಿದೆ. ಈ ಪುರಾವೆಯಲ್ಲಿ, ಸರಳತೆಗಾಗಿ ಕ್ವಾಂಟಿಫೈಯರ್ ಪಟ್ಟಿಯು ಅಸ್ತಿತ್ವವಾದದ ಅರ್ಹತೆಯೊಂದಿಗೆ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ ಮತ್ತು ಕೊನೆಗೊಳ್ಳುತ್ತದೆ ಎಂದು ನಾವು ಭಾವಿಸುತ್ತೇವೆ. ಯಾವುದೇ ಅಭಿವ್ಯಕ್ತಿಯನ್ನು siಯಲ್ಲಿ ಕಾಣಿಸದ ನಕಲಿ ಅಸ್ಥಿರಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಈ ರೂಪಕ್ಕೆ ಪರಿವರ್ತಿಸಬಹುದು ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಮೇಲೆ ತೋರಿಸಿರುವಂತೆ ಗ್ರಾಫ್ ಜಿ ಅನ್ನು ನಿರ್ಮಿಸುವ ಮೂಲಕ, ಫಾರ್ಮುಲಾ-ಗೇಮ್ನ ಯಾವುದೇ ನಿದರ್ಶನವನ್ನು ಸಾಮಾನ್ಯೀಕೃತ ಭೌಗೋಳಿಕತೆಯ ನಿದರ್ಶನಕ್ಕೆ ಇಳಿಸಬಹುದು ಎಂದು ನಾವು ತೋರಿಸುತ್ತೇವೆ, ಅಲ್ಲಿ ಪಿ1ಗೆ ಸೂಕ್ತವಾದ ಕಾರ್ಯತಂತ್ರವು ಪೀಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಮತ್ತು ಪಿ2ಗೆ ಸೂಕ್ತವಾದ ಕಾರ್ಯತಂತ್ರವು ಪೀಗೆ ಸಮನಾಗಿರುತ್ತದೆ. ನೋಡ್ಗಳ ಎಡ ಲಂಬ ಸರಪಳಿಯನ್ನು ಫಾರ್ಮುಲಾ-ಗೇಮ್ನಲ್ಲಿನ ಅಸ್ಥಿರಗಳಿಗೆ ಮೌಲ್ಯಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ವಿಧಾನವನ್ನು ಅನುಕರಿಸಲು ವಿನ್ಯಾಸಗೊಳಿಸಲಾಗಿದೆ. ಪ್ರತಿಯೊಂದು ವಜ್ರದ ರಚನೆಯು ಪ್ರಮಾಣೀಕೃತ ವೇರಿಯೇಬಲ್ಗೆ ಅನುರೂಪವಾಗಿದೆ. ಪ್ರತಿ ಬ್ರಾಂಚಿಂಗ್ ನೋಡ್ನಲ್ಲಿ ಆಟಗಾರರು ತಿರುವುಗಳಲ್ಲಿ ಮಾರ್ಗಗಳನ್ನು ನಿರ್ಧರಿಸುತ್ತಾರೆ. ಮೊದಲ ಕ್ವಾಂಟಿಫೈಯರ್ ಎಕ್ಸಿಸ್ಟೆನ್ಶಿಯಲ್ ಆಗಿರುತ್ತದೆ ಎಂದು ನಾವು ಭಾವಿಸಿದ್ದರಿಂದ, ಪಿ1 ಮೊದಲು ಹೋಗುತ್ತದೆ, x1 ನಿಜವಾಗಿದ್ದರೆ ಎಡ ನೋಡ್ ಅನ್ನು ಮತ್ತು x1 ತಪ್ಪಾಗಿದ್ದರೆ ಬಲ ನೋಡ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ಪ್ರತಿ ಆಟಗಾರನು ನಂತರ ಬಲವಂತದ ತಿರುವುಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳಬೇಕು, ಮತ್ತು ನಂತರ ಪಿ2 x2 ಗೆ ಒಂದು ಮೌಲ್ಯವನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ಈ ಪರ್ಯಾಯ ನಿಯೋಜನೆಗಳು ಎಡಭಾಗದಲ್ಲಿ ಮುಂದುವರಿಯುತ್ತವೆ. ಇಬ್ಬರೂ ಆಟಗಾರರು ಎಲ್ಲಾ ವಜ್ರಗಳನ್ನು ದಾಟಿದ ನಂತರ, ಅದು ಮತ್ತೆ ಪಿ1ನ ಸರದಿ, ಏಕೆಂದರೆ ಕೊನೆಯ ಕ್ವಾಂಟಿಫೈಯರ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ ಎಂದು ನಾವು ಭಾವಿಸಿದ್ದೆವು. ಗ್ರಾಫ್ನ ಬಲಭಾಗಕ್ಕೆ ಹೋಗುವ ಮಾರ್ಗವನ್ನು ಅನುಸರಿಸುವುದನ್ನು ಬಿಟ್ಟು ಪಿ1ಗೆ ಬೇರೆ ಆಯ್ಕೆ ಇಲ್ಲ. ನಂತರ ಚಲಿಸುವ ಪಿ2 ಸರದಿ. ಆಟವು ಗ್ರಾಫ್ನ ಬಲಭಾಗಕ್ಕೆ ಬಂದಾಗ, ಅದು ಫಾರ್ಮುಲಾ ಆಟದಲ್ಲಿ ಆಟದ ಅಂತ್ಯವನ್ನು ಹೋಲುತ್ತದೆ. ಫಾರ್ಮುಲಾ ಆಟದಲ್ಲಿ, ಪೀ ಯು ನಿಜವಾಗಿದ್ದರೆ ಗೆಲ್ಲುತ್ತದೆ, ಆದರೆ ಪೀ ಯು ತಪ್ಪಾಗಿದ್ದರೆ ಗೆಲ್ಲುತ್ತದೆ ಎಂಬುದನ್ನು ನೆನಪಿಸಿಕೊಳ್ಳಿ. ಗ್ರಾಫ್ನ ಬಲಭಾಗವು ಪೆ ಗೆದ್ದರೆ ಮಾತ್ರ ಪಿ1 ಗೆಲ್ಲುತ್ತದೆ ಮತ್ತು ಪಾ ಗೆದ್ದರೆ ಮಾತ್ರ ಪಿ2 ಗೆಲ್ಲುತ್ತದೆ ಎಂದು ಖಾತರಿಪಡಿಸುತ್ತದೆ. ಪಾ ಗೆದ್ದಾಗ ಪಿ2 ಯಾವಾಗಲೂ ಗೆಲ್ಲುತ್ತದೆ ಎಂದು ಮೊದಲು ನಾವು ತೋರಿಸುತ್ತೇವೆ. ಪಾ ಗೆದ್ದರೆ, si ಸುಳ್ಳು. si ತಪ್ಪಾಗಿದ್ದರೆ, ಅತೃಪ್ತಿಕರ ಷರತ್ತು ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ. ಪಿ2 ಗೆಲ್ಲಲು ಅತೃಪ್ತಿಕರ ಷರತ್ತನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ನಂತರ ಪಿ1ನ ಸರದಿ ಬಂದಾಗ ಅವನು ಪಿ2 ಆಯ್ಕೆ ಮಾಡಿದ ಆ ಷರತ್ತಿನಲ್ಲಿ ಅಕ್ಷರಶಃ ಒಂದನ್ನು ಆಯ್ಕೆ ಮಾಡಬೇಕು. ಷರತ್ತಿನಲ್ಲಿರುವ ಎಲ್ಲಾ ಅಕ್ಷರಗಳು ಸುಳ್ಳಾಗಿರುವುದರಿಂದ, ಅವು ಎಡ ಲಂಬ ಸರಪಳಿಯಲ್ಲಿ ಹಿಂದೆ ಭೇಟಿ ನೀಡಿದ ನೋಡ್ಗಳಿಗೆ ಸಂಪರ್ಕ ಹೊಂದಿರುವುದಿಲ್ಲ. ಇದು ಎಡ ಸರಪಳಿಯ ವಜ್ರದಲ್ಲಿ ಅನುಗುಣವಾದ ನೋಡ್ಗೆ ಸಂಪರ್ಕವನ್ನು ಅನುಸರಿಸಲು ಮತ್ತು ಅದನ್ನು ಆಯ್ಕೆ ಮಾಡಲು ಪಿ 2 ಗೆ ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಪಿ1 ಈಗ ಯಾವುದೇ ಪಕ್ಕದ ನೋಡ್ಗಳು ಮತ್ತು ನಷ್ಟಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡಲು ಸಾಧ್ಯವಾಗುತ್ತಿಲ್ಲ. ಪೆ ಗೆದ್ದಾಗ ಪಿ1 ಯಾವಾಗಲೂ ಗೆಲ್ಲುತ್ತದೆ ಎಂದು ಈಗ ನಾವು ತೋರಿಸುತ್ತೇವೆ. ಪೆ ಗೆದ್ದರೆ, si ನಿಜವಾಗಿದೆ. si ನಿಜವಾಗಿದ್ದರೆ, ಗ್ರಾಫ್ನ ಬಲಭಾಗದಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಷರತ್ತು ನಿಜವಾದ ಅಕ್ಷರವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಪಿ2 ಯಾವುದೇ ಷರತ್ತನ್ನು ಆಯ್ಕೆ ಮಾಡಬಹುದು. ನಂತರ ಪಿ1 ಸತ್ಯವಾದ ಅಕ್ಷರವನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ಮತ್ತು ಇದು ನಿಜವಾಗಿರುವುದರಿಂದ, ಎಡ ಲಂಬ ನೋಡ್ನಲ್ಲಿರುವ ಅದರ ಪಕ್ಕದ ನೋಡ್ ಅನ್ನು ಈಗಾಗಲೇ ಆಯ್ಕೆ ಮಾಡಲಾಗಿದೆ, ಆದ್ದರಿಂದ ಪಿ 2 ಗೆ ಮಾಡಲು ಮತ್ತು ಕಳೆದುಕೊಳ್ಳಲು ಯಾವುದೇ ಚಲನೆಗಳಿಲ್ಲ. ಪ್ಲ್ಯಾನರ್ ಸಾಮಾನ್ಯೀಕೃತ ಭೌಗೋಳಿಕತೆಯು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಸಂಪೂರ್ಣ ಸಾಮಾನ್ಯೀಕೃತ ಭೌಗೋಳಿಕತೆಯು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣವಾಗಿದೆ, ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಆಡಿದಾಗಲೂ ಸಹ. ಈ ಕೆಳಗಿನ ಪುರಾವೆಯು 3ನೇ ಪ್ರಮೇಯದಿಂದ ಬಂದಿದೆ. ಪ್ಲ್ಯಾನರ್ ಜಿ. ಜಿ. ಯು ಜಿ. ಜಿ. ಯ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿರುವುದರಿಂದ ಮತ್ತು ಜಿ. ಜಿ. ಯು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ನಲ್ಲಿರುವುದರಿಂದ, ಪ್ಲ್ಯಾನರ್ ಜಿ. ಜಿ. ಯು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ನಲ್ಲಿದೆ. ಪ್ಲ್ಯಾನರ್ ಜಿ. ಜಿ. ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಹಾರ್ಡ್ ಎಂದು ತೋರಿಸಲು ಉಳಿದಿದೆ. ಅನಿಯಂತ್ರಿತ ರೇಖಾಚಿತ್ರವನ್ನು ಸಮತಟ್ಟಾದ ರೇಖಾಚಿತ್ರವಾಗಿ ಹೇಗೆ ಪರಿವರ್ತಿಸುವುದು ಎಂಬುದನ್ನು ತೋರಿಸುವ ಮೂಲಕ ಇದನ್ನು ಸಾಬೀತುಪಡಿಸಬಹುದು, ಅಂದರೆ ಈ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಆಡುವ ಜಿ. ಜಿ ಆಟವು ಮೂಲ ರೇಖಾಚಿತ್ರದಂತೆಯೇ ಅದೇ ಫಲಿತಾಂಶವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಅದನ್ನು ಮಾಡಲು, ಮೂಲ ಗ್ರಾಫ್ನ ಎಲ್ಲಾ ಅಂಚಿನ ಕ್ರಾಸಿಂಗ್ಗಳನ್ನು ತೆಗೆದುಹಾಕುವುದು ಮಾತ್ರ ಅಗತ್ಯವಾಗಿದೆ. ಒಂದು ಹಂತದಲ್ಲಿ ಯಾವುದೇ ಮೂರು ಅಂಚುಗಳು ಛೇದಿಸದ ರೀತಿಯಲ್ಲಿ ನಾವು ರೇಖಾಚಿತ್ರವನ್ನು ರಚಿಸುತ್ತೇವೆ ಮತ್ತು ಒಂದೇ ಆಟದಲ್ಲಿ ಯಾವುದೇ ಜೋಡಿ ದಾಟುವ ಅಂಚುಗಳನ್ನು ಬಳಸಲಾಗುವುದಿಲ್ಲ. ಇದು ಸಾಮಾನ್ಯವಾಗಿ ಸಾಧ್ಯವಿಲ್ಲ, ಆದರೆ ಫಾರ್ಮುಲಾ-ಗೇಮ್ ಉದಾಹರಣೆಯಿಂದ ನಿರ್ಮಿಸಲಾದ ಗ್ರಾಫ್ಗೆ ಯಾವಾಗಲೂ ಸಾಧ್ಯವಿದೆ; ಉದಾಹರಣೆಗೆ ನಾವು ಕ್ರಾಸಿಂಗ್ಗಳಲ್ಲಿ ಒಳಗೊಂಡಿರುವ ಷರತ್ತು ಶೃಂಗಗಳ ಅಂಚುಗಳನ್ನು ಮಾತ್ರ ಹೊಂದಬಹುದು. ಈಗ ನಾವು ಪ್ರತಿ ಕ್ರಾಸಿಂಗ್ ಅನ್ನು ಈ ರಚನೆಯೊಂದಿಗೆ ಬದಲಾಯಿಸುತ್ತೇವೆಃ ಫಲಿತಾಂಶವು ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ ಆಗಿದೆ, ಮತ್ತು ಅದೇ ಆಟಗಾರನು ಮೂಲ ಗ್ರಾಫ್ನಲ್ಲಿರುವಂತೆ ಗೆಲುವನ್ನು ಒತ್ತಾಯಿಸಬಹುದುಃ ಆಟಗಾರನು ರೂಪಾಂತರಗೊಂಡ ಆಟದಲ್ಲಿ V ಯಿಂದ "ಮೇಲಕ್ಕೆ" ಹೋಗಲು ಆಯ್ಕೆ ಮಾಡಿದರೆ, ನಂತರ ಇಬ್ಬರೂ ಆಟಗಾರರು "ಮೇಲಕ್ಕೆ" ಹೋಗುವುದನ್ನು ಮುಂದುವರಿಸಬೇಕು ಅಥವಾ ತಕ್ಷಣವೇ ಸೋಲಬೇಕು. ಆದ್ದರಿಂದ ರೂಪಾಂತರಗೊಂಡ ಆಟದಲ್ಲಿ V ಯಿಂದ "ಮೇಲಕ್ಕೆ" ಚಲಿಸುವುದು ಮೂಲ ಆಟದಲ್ಲಿ V → W ಚಲನೆಯನ್ನು ಅನುಕರಿಸುತ್ತದೆ. V → W ಒಂದು ಗೆಲುವಿನ ಕ್ರಮವಾಗಿದ್ದರೆ, ರೂಪಾಂತರಗೊಂಡ ಆಟದಲ್ಲಿ V ಯಿಂದ "ಮೇಲಕ್ಕೆ" ಚಲಿಸುವುದು ಸಹ ಗೆಲುವಿನ ಕ್ರಮವಾಗಿದೆ, ಮತ್ತು ಪ್ರತಿಯಾಗಿ. ಹೀಗಾಗಿ, ರೂಪಾಂತರಗೊಂಡ ಗ್ರಾಫ್ನಲ್ಲಿ ಆಡುವ ಜಿ. ಜಿ. ಆಟವು ಮೂಲ ಗ್ರಾಫ್ನಂತೆಯೇ ಅದೇ ಫಲಿತಾಂಶವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಈ ರೂಪಾಂತರವು ಮೂಲ ಗ್ರಾಫ್ನಲ್ಲಿರುವ ಅಂಚಿನ ಛೇದಕಗಳ ಸಂಖ್ಯೆಗೆ ಸ್ಥಿರವಾದ ಗುಣಾಕಾರವಾದ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಹೀಗಾಗಿ ಇದು ಬಹುಪದ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಹೀಗಾಗಿ ಪ್ಲ್ಯಾನರ್ ಜಿ. ಜಿ. ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ. ಗರಿಷ್ಠ ಡಿಗ್ರಿ 3 ರೊಂದಿಗೆ ಪ್ಲ್ಯಾನರ್ ಬೈಪಾರ್ಟೈಟ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಆಡುವ ಗರಿಷ್ಠ ಡಿಗ್ರಿ 3 ಜಿಜಿಯೊಂದಿಗೆ ಪ್ಲ್ಯಾನರ್ ಬೈಪಾರ್ಟೈಟ್ ಗ್ರಾಫ್ ಇನ್ನೂ ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣವಾಗಿದೆ, 3 ಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಡಿಗ್ರಿ ಶೃಂಗಗಳನ್ನು ಬದಲಾಯಿಸುವ ಮೂಲಕ ಗರಿಷ್ಠ ಡಿಗ್ರಿ 3 ರೊಂದಿಗೆ ಶೃಂಗಗಳ ಸರಪಳಿಯೊಂದಿಗೆ. ಪುರಾವೆ ಇದೆ. ಮತ್ತು ಈ ಕೆಳಗಿನ ರಚನೆಯನ್ನು ಬಳಸುತ್ತಾರೆಃ ಒಬ್ಬ ಆಟಗಾರನು ಈ ರಚನೆಯ ಯಾವುದೇ ಪ್ರವೇಶದ್ವಾರವನ್ನು ಬಳಸಿದರೆ, ಇನ್ನೊಬ್ಬ ಆಟಗಾರನು ಯಾವ ನಿರ್ಗಮನವನ್ನು ಬಳಸಬೇಕೆಂದು ಆಯ್ಕೆ ಮಾಡುತ್ತಾನೆ. ಅಲ್ಲದೆ, ನಿರ್ಮಾಣವನ್ನು ಒಮ್ಮೆ ಮಾತ್ರ ಹಾದುಹೋಗಬಹುದು, ಏಕೆಂದರೆ ಕೇಂದ್ರ ಶೃಂಗವನ್ನು ಯಾವಾಗಲೂ ಭೇಟಿ ಮಾಡಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ ಈ ರಚನೆಯು ಮೂಲ ಶೃಂಗಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ಜಿಜಿಯ ಒಂದು ರೂಪಾಂತರವನ್ನು ಅಂಚಿನ ಭೌಗೋಳಿಕತೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಅಲ್ಲಿ ಪ್ರತಿ ಚಲನೆಯ ನಂತರ, ಆಟಗಾರನು ಹಾದುಹೋಗುವ ಅಂಚನ್ನು ಅಳಿಸಲಾಗುತ್ತದೆ. ಇದು ಮೂಲ ಜಿ. ಜಿ. ಗೆ ವ್ಯತಿರಿಕ್ತವಾಗಿದೆ, ಅಲ್ಲಿ ಪ್ರತಿ ಚಲನೆಯ ನಂತರ, ಆಟಗಾರನು ಬಳಸುತ್ತಿದ್ದ ಶೃಂಗವನ್ನು ಅಳಿಸಲಾಗುತ್ತದೆ. ಈ ದೃಷ್ಟಿಕೋನದಲ್ಲಿ, ಮೂಲ ಜಿ. ಜಿ. ಯನ್ನು ವೆರ್ಟೆಕ್ಸ್ ಜಿಯಾಗ್ರಫಿ ಎಂದು ಕರೆಯಬಹುದು. ಅಂಚಿನ ಭೌಗೋಳಿಕತೆಯು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಸಂಪೂರ್ಣವಾಗಿದೆ. ಶೃಂಗದ ಭೌಗೋಳಿಕತೆಗೆ ಬಳಸಿದ ಅದೇ ರಚನೆಯನ್ನು ಇದನ್ನು ಬಳಸಬಹುದೆಂದು ಸಾಬೀತುಪಡಿಸಬಹುದು. ನಿರ್ದೇಶನವಿಲ್ಲದ ಭೌಗೋಳಿಕತೆಯು ನಿರ್ದೇಶನವಿಲ್ಲದ ಗ್ರಾಫ್ನಲ್ಲಿ ಭೌಗೋಳಿಕ ಆಟವನ್ನು ಆಡುವುದನ್ನು ಸಹ ಪರಿಗಣಿಸಬಹುದು (ಅಂದರೆ, ಅಂಚುಗಳನ್ನು ಎರಡೂ ದಿಕ್ಕುಗಳಲ್ಲಿ ಹಾದುಹೋಗಬಹುದು). ಫ್ರಾಂಕೆಲ್, ಶೈನರ್ಮನ್ ಮತ್ತು ಉಲ್ಮನ್ ನಿರ್ದೇಶಿಸದ ಶೃಂಗದ ಭೌಗೋಳಿಕತೆಯನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು ಎಂದು ತೋರಿಸುತ್ತಾರೆ, ಆದರೆ ನಿರ್ದೇಶಿಸದ ಅಂಚಿನ ಭೌಗೋಳಿಕತೆಯು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣವಾಗಿದೆ, ಗರಿಷ್ಠ ಡಿಗ್ರಿ 3 ಹೊಂದಿರುವ ಸಮತಟ್ಟಾದ ಗ್ರಾಫ್ಗಳಿಗೂ ಸಹ. ರೇಖಾಚಿತ್ರವು ಉಭಯಪಕ್ಷೀಯವಾಗಿದ್ದರೆ, ನಿರ್ದೇಶಿಸದ ಅಂಚಿನ ಭೂಗೋಳವನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಪರಿಣಾಮಗಳು ಜಿ. ಜಿ. ಯು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಕಂಪ್ಲೀಟ್ ಆಗಿರುವುದರಿಂದ, ಪಿ = ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ ಹೊರತು ಜಿ. ಜಿ. ಯಲ್ಲಿ ಸೂಕ್ತವಾದ ಆಟಕ್ಕೆ ಯಾವುದೇ ಬಹುಪದ ಸಮಯದ ಕ್ರಮಾವಳಿ ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲ. ಆದಾಗ್ಯೂ, ಇತರ ಆಟಗಳ ಸಂಕೀರ್ಣತೆಯನ್ನು ಸಾಬೀತುಪಡಿಸುವುದು ಅಷ್ಟು ಸುಲಭವಲ್ಲದಿರಬಹುದು ಏಕೆಂದರೆ ಕೆಲವು ಆಟಗಳು (ಚದುರಂಗದಂತಹವು) ಸೀಮಿತ ಸಂಖ್ಯೆಯ ಆಟದ ಸ್ಥಾನಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ-ಇದು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆಗೆ ಮ್ಯಾಪಿಂಗ್ ಅನ್ನು ರೂಪಿಸಲು ಕಷ್ಟವಾಗುತ್ತದೆ (ಅಥವಾ ಅಸಾಧ್ಯ). ಇದರ ಹೊರತಾಗಿಯೂ, ಕೆಲವು ಆಟಗಳ ಸಂಕೀರ್ಣತೆಯನ್ನು ಇನ್ನೂ ಸಾಮಾನ್ಯೀಕರಣದ ಮೂಲಕ ವಿಶ್ಲೇಷಿಸಬಹುದು (ಉದಾಹರಣೆಗೆ, ಒಂದು n × n ಫಲಕಕ್ಕೆ). ಜಿ. ಜಿ. ಯ ಸಂಪೂರ್ಣತೆಯ ಪುರಾವೆಯಾಗಿ, ಸಾಮಾನ್ಯೀಕೃತ ಗೋದ ಪುರಾವೆಗಾಗಿ ಉಲ್ಲೇಖಗಳನ್ನು ನೋಡಿ. ಉಲ್ಲೇಖಗಳು ಮೈಕೆಲ್ ಸಿಪ್ಸರ್, ಇಂಟ್ರೊಡಕ್ಷನ್ ಟು ದಿ ಥಿಯರಿ ಆಫ್ ಕಂಪ್ಯೂಟೇಶನ್, ಪಿಡಬ್ಲ್ಯೂಎಸ್, 1997. ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳು