Vertex enumeration problem
ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ಪಾಲಿಟೋಪ್, ಪಾಲಿಹೆಡ್ರಲ್ ಕೋಶ ಸಂಕೀರ್ಣ, ಹೈಪರ್ಪ್ಲೇನ್ ಜೋಡಣೆ, ಅಥವಾ ವಿವಿಕ್ತ ರೇಖಾಗಣಿತದ ಇತರ ವಸ್ತುಗಳಿಗೆ ಶೃಂಗ ಎಣಿಕೆ ಸಮಸ್ಯೆಯು ವಸ್ತುವಿನ ಕೆಲವು ಔಪಚಾರಿಕ ಪ್ರಾತಿನಿಧ್ಯವನ್ನು ನೀಡಿದ ವಸ್ತುವಿನ ಶೃಂಗಗಳನ್ನು ನಿರ್ಧರಿಸುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ರೇಖೀಯ ಅಸಮಾನತೆಗಳ ಗುಂಪಿನಿಂದ ನಿರ್ದಿಷ್ಟಪಡಿಸಲಾದ ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಟೋಪ್ನ ಶೃಂಗಗಳ ಎಣಿಕೆಯ ಸಮಸ್ಯೆಯು ಒಂದು ಶಾಸ್ತ್ರೀಯ ಉದಾಹರಣೆಯಾಗಿದೆಃ ಇಲ್ಲಿ A ಎಂಬುದು m × n ಮ್ಯಾಟ್ರಿಕ್ಸ್, x ಎಂಬುದು ಅಸ್ಥಿರಗಳ n × 1 ಕಾಲಮ್ ವೆಕ್ಟರ್, ಮತ್ತು b ಎಂಬುದು ಸ್ಥಿರಾಂಕಗಳ m × 1 ಕಾಲಮ್ ವೆಕ್ಟರ್ ಆಗಿದೆ. ಶೃಂಗಗಳನ್ನು ನೀಡಿದ ಮಿತಿಯ ಅಸಮಾನತೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವ ವಿಲೋಮ (ಉಭಯ) ಸಮಸ್ಯೆಯನ್ನು ಮುಖದ ಎಣಿಕೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ (ಕನ್ವೆಕ್ಸ್ ಹಲ್ ಕ್ರಮಾವಳಿಗಳನ್ನು ನೋಡಿ). ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಮಸ್ಯೆಯ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯು ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ ಸಂಶೋಧನೆಯ ವಿಷಯವಾಗಿದೆ. ಮಿತಿಯಿಲ್ಲದ ಪಾಲಿಹೆಡ್ರಾದಲ್ಲಿ, ಸಮಸ್ಯೆಯನ್ನು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಹೆಚ್ಚು ನಿಖರವಾಗಿ, ಪಿ = ಎನ್ಪಿ ಹೊರತು, ಸಂಯೋಜಿತ ಇನ್ಪುಟ್-ಔಟ್ಪುಟ್ ಗಾತ್ರದಲ್ಲಿ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ಯಾವುದೇ ಅಲ್ಗಾರಿದಮ್ ಇಲ್ಲ. ಡೇವಿಡ್ ಅವಿಸ್ ಮತ್ತು ಕೊಮಿ ಫುಕುಡಾ ಅವರ 1992 ರ ಲೇಖನವು ರಿವರ್ಸ್-ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತದೆ, ಇದು ಡಿ ಆಯಾಮಗಳಲ್ಲಿ n ಅಸಮಾನತೆಗಳ ನಾನ್ಡಿಜೆನೆರೇಟ್ ವ್ಯವಸ್ಥೆಯಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಪಾಲಿಟೋಪ್ನ ವಿ ಶೃಂಗಗಳನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ (ಅಥವಾ, ದ್ವಿಮುಖವಾಗಿ, ಡಿ ಆಯಾಮಗಳಲ್ಲಿ ಎನ್ ಬಿಂದುಗಳ ಕನ್ವೆಕ್ಸ್ ಹಲ್ನ ವಿ ಮುಖಗಳು, ಅಲ್ಲಿ ಪ್ರತಿ ಮುಖವು ನಿಖರವಾಗಿ ಡಿ ನೀಡಲಾದ ಬಿಂದುಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ) ಸಮಯ ಒ (ಎನ್ಡಿವಿ) ಮತ್ತು ಸ್ಪೇಸ್ ಒ (ಎನ್ಡಿ). ಡಿ ಆಯಾಮಗಳಲ್ಲಿ ಎನ್ ಹೈಪರ್ ಪ್ಲೇನ್ಗಳ ಸರಳ ಜೋಡಣೆಯಲ್ಲಿರುವ ವಿ ಶೃಂಗಗಳನ್ನು ಒ (ಎನ್2ಡಿವಿ) ಸಮಯ ಮತ್ತು ಒ (ಎನ್ಡಿ) ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯಲ್ಲಿ ಕಾಣಬಹುದು. ಅವಿಸ್-ಫುಕುಡಾ ಅಲ್ಗಾರಿದಮ್ ಓರಿಯೆಂಟೆಡ್ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳಿಗಾಗಿ ಕ್ರಿಸ್-ಕ್ರಾಸ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಅಳವಡಿಸಿಕೊಂಡಿದೆ. ಟಿಪ್ಪಣಿಗಳು ಉಲ್ಲೇಖಗಳು ರೇಖಾತ್ಮಕ ಕ್ರಮಾವಳಿಗಳು ಪಾಲಿಹೆಡ್ರಲ್ ಕಾಂಬಿನೇಟರಿಕ್ಸ್ ಪಾಲಿಹೆಡ್ರಲ್ ಡಿಸ್ಕ್ರೀಟ್ ಜ್ಯಾಮಿತಿ ಎನ್ಯೂಮರೇಟಿವ್ ಕಾಂಬಿನೇಟರಿಕ್ಸ್ ಗಣಿತದ ಸಮಸ್ಯೆಗಳು ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿ