Sparse language
ಕಂಪ್ಯೂಟೇಶನಲ್ ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ವಿರಳವಾದ ಭಾಷೆಯು ಒಂದು ಔಪಚಾರಿಕ ಭಾಷೆಯಾಗಿದ್ದು (ತಂತಿಗಳ ಒಂದು ಗುಂಪು), ಭಾಷೆಯಲ್ಲಿ n ಉದ್ದದ ತಂತಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸುವ ಸಂಕೀರ್ಣತೆಯ ಕಾರ್ಯವು n ನ ಬಹುಪದ ಕಾರ್ಯದಿಂದ ಸುತ್ತುವರಿಯಲ್ಪಟ್ಟಿದೆ. ಅವುಗಳನ್ನು ಪ್ರಾಥಮಿಕವಾಗಿ ಇತರ ವರ್ಗಗಳೊಂದಿಗೆ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗ NP ಯ ಸಂಬಂಧದ ಅಧ್ಯಯನದಲ್ಲಿ ಬಳಸಲಾಗುತ್ತದೆ. ಎಲ್ಲಾ ವಿರಳ ಭಾಷೆಗಳ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗವನ್ನು ಸ್ಪಾರ್ಸ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ವಿರಳ ಭಾಷೆಗಳನ್ನು ವಿರಳ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಏಕೆಂದರೆ ಒಟ್ಟು n ಉದ್ದದ 2n ತಂತಿಗಳಿವೆ, ಮತ್ತು ಒಂದು ಭಾಷೆಯು ಬಹುಪದದಲ್ಲಿ ಇವುಗಳಲ್ಲಿ ಹೆಚ್ಚಿನವುಗಳನ್ನು ಮಾತ್ರ ಹೊಂದಿದ್ದರೆ, ಅದು ಹೊಂದಿರುವ n ಉದ್ದದ ತಂತಿಗಳ ಪ್ರಮಾಣವು n ಬೆಳೆದಂತೆ ವೇಗವಾಗಿ ಶೂನ್ಯಕ್ಕೆ ಹೋಗುತ್ತದೆ. ಎಲ್ಲಾ ಯುನರಿ ಭಾಷೆಗಳು ವಿರಳವಾಗಿವೆ. ಕ್ಷುಲ್ಲಕವಲ್ಲದ ವಿರಳ ಭಾಷೆಯ ಒಂದು ಉದಾಹರಣೆಯೆಂದರೆ ಕೆಲವು ಸ್ಥಿರ k ಗೆ ನಿಖರವಾಗಿ k 1 ಬಿಟ್ಗಳನ್ನು ಹೊಂದಿರುವ ಬೈನರಿ ತಂತಿಗಳ ಗುಂಪಾಗಿದೆ; ಪ್ರತಿ n ಗೆ, ಭಾಷೆಯಲ್ಲಿ ಕೇವಲ ತಂತಿಗಳಿವೆ, ಇದು nk ನಿಂದ ಸುತ್ತುವರಿಯಲ್ಪಟ್ಟಿದೆ. ಇತರ ಸಂಕೀರ್ಣತೆ ವರ್ಗಗಳೊಂದಿಗಿನ ಸಂಬಂಧಗಳು SPARSE ಯು ಟ್ಯಾಲಿ ಎಂಬ ಯೂನರಿ ಭಾಷೆಗಳ ವರ್ಗವನ್ನು ಒಳಗೊಂಡಿದೆ, ಏಕೆಂದರೆ ಇವು ಯಾವುದೇ ಒಂದು ಉದ್ದದ ಗರಿಷ್ಠ ಒಂದು ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಪಿ/ಪಾಲಿಯಲ್ಲಿನ ಎಲ್ಲಾ ಭಾಷೆಗಳು ವಿರಳವಾಗಿಲ್ಲದಿದ್ದರೂ, ಪಿ/ಪಾಲಿಯಲ್ಲಿನ ಯಾವುದೇ ಭಾಷೆಯಿಂದ ವಿರಳವಾದ ಭಾಷೆಗೆ ಬಹುಪದ-ಸಮಯದ ಟ್ಯೂರಿಂಗ್ ಕಡಿತವಿದೆ. ಯಾವುದೇ ವಿರಳ ಭಾಷೆಯು ಸಹ-ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿದ್ದರೆ, ಪಿ = ಎನ್. ಪಿ.; ಯಾವುದೇ ವಿರಳ ಭಾಷೆಯು ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿದ್ದರೆ, ಪಿ = ಎನ್. ಪಿ. (ಇದು ಮಹಾನಿಯ ಪ್ರಮೇಯ) ಎಂದು 1982ರಲ್ಲಿ ತೋರಿಸಲು ಮಹಾನಿಯವರು ಇದನ್ನು ಬಳಸಿದ್ದಾರೆ ಎಂದು ಫಾರ್ಚೂನ್ 1979ರಲ್ಲಿ ತೋರಿಸಿತು. ಲೆಫ್ಟ್-ಸೆಟ್ಗಳ ಆಧಾರದ ಮೇಲೆ ಇದಕ್ಕೆ ಸರಳವಾದ ಪುರಾವೆಯನ್ನು 1991ರಲ್ಲಿ ಓಗಿಹಾರಾ ಮತ್ತು ವತನಾಬೆ ನೀಡಿದರು. ಮಾಹಾನಿಯವರ ವಾದವು ವಾಸ್ತವವಾಗಿ ವಿರಳ ಭಾಷೆಯು ಎನ್. ಪಿ. ಯಲ್ಲಿರಬೇಕಾಗಿಲ್ಲ (ಏಕೆಂದರೆ ಎನ್. ಪಿ.-ಕಠಿಣ ವಿರಳ ಗುಂಪಿನ ಅಸ್ತಿತ್ವವು ಎನ್. ಪಿ.-ಪೂರ್ಣ ವಿರಳ ಗುಂಪಿನ ಅಸ್ತಿತ್ವವನ್ನು ಸೂಚಿಸುತ್ತದೆ), ಆದ್ದರಿಂದ ಪಿ = ಎನ್. ಪಿ. ಆಗಿದ್ದರೆ ಮಾತ್ರ ವಿರಳವಾದ ಎನ್. ಪಿ.-ಕಠಿಣ ಗುಂಪು ಇರುತ್ತದೆ. ಇದಲ್ಲದೆ, ಎನ್. ಪಿ. ಯಲ್ಲಿ ಪಿ. ಯಲ್ಲಿಲ್ಲದ ವಿರಳ ಭಾಷೆಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ ಮಾತ್ರ ಮತ್ತು ಇದ್ದರೆ ಮಾತ್ರ, ಎನ್. ಪಿ.-ಪೂರ್ಣ ಭಾಷೆಯಿಂದ ವಿರಳ ಭಾಷೆಗೆ ಟ್ಯೂರಿಂಗ್ ಕಡಿತ (ಮಹಾನಿಯ ಪ್ರಮೇಯದಿಂದ ಕಾರ್ಪ್ ಕಡಿತಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ) ಇರುತ್ತದೆ. 1999 ರಲ್ಲಿ, ಜಿನ್-ಯಿ ಕೈ ಮತ್ತು ಡಿ. ಶಿವಕುಮಾರ್, ಓಗಿಹಾರ ಅವರ ಕೆಲಸವನ್ನು ನಿರ್ಮಿಸುತ್ತಾ, ವಿರಳವಾದ ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆ ಇದ್ದರೆ, ಎಲ್ = ಪಿ. ಬಾಹ್ಯ ಉಲ್ಲೇಖಗಳು ಲ್ಯಾನ್ಸ್ ಫೋರ್ಟ್ನೋವನ್ನು ಸಂಪರ್ಕಿಸುತ್ತವೆ ಎಂದು ತೋರಿಸಿದರು. ನೆಚ್ಚಿನ ಪ್ರಮೇಯಗಳುಃ ಸಣ್ಣ ಸೆಟ್ಗಳು. ಏಪ್ರಿಲ್ 18,2006. ವಿಲಿಯಂ ಗ್ಯಾಸಾರ್ಚ್. ವಿರಳ ಸೆಟ್ಗಳು (ಮಹಾನಿಯವರಿಗೆ ಗೌರವ). ಜೂನ್ 29,2007. ಔಪಚಾರಿಕ ಭಾಷೆಗಳು ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತ