Unary language
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಯೂನರಿ ಭಾಷೆ ಅಥವಾ ಟ್ಯಾಲಿ ಭಾಷೆಯು ಒಂದು ಔಪಚಾರಿಕ ಭಾಷೆಯಾಗಿದೆ (ತಂತಿಗಳ ಒಂದು ಗುಂಪು), ಅಲ್ಲಿ ಎಲ್ಲಾ ತಂತಿಗಳು 1k ರೂಪವನ್ನು ಹೊಂದಿರುತ್ತವೆ, ಅಲ್ಲಿ "1" ಯಾವುದೇ ಸ್ಥಿರ ಸಂಕೇತವಾಗಿರಬಹುದು. ಉದಾಹರಣೆಗೆ, {1,111,1111} ಭಾಷೆಯು ಏಕರೂಪವಾಗಿದೆ, ಹಾಗೆಯೇ ಭಾಷೆಯು {1k | k ಅವಿಭಾಜ್ಯವಾಗಿದೆ}. ಅಂತಹ ಎಲ್ಲಾ ಭಾಷೆಗಳ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗವನ್ನು ಕೆಲವೊಮ್ಮೆ ಟಾಲಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. "ಯೂನರಿ" ಎಂಬ ಹೆಸರು ಯೂನರಿ ಭಾಷೆಯು ಯೂನರಿ ಸಂಖ್ಯಾ ವ್ಯವಸ್ಥೆಯಲ್ಲಿ ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳ ಗುಂಪಿನ ಸಂಕೇತವಾಗಿದೆ ಎಂಬ ಅಂಶದಿಂದ ಬಂದಿದೆ. ಯಾವುದೇ ಸೀಮಿತ ವರ್ಣಮಾಲೆಯ ಮೇಲಿನ ತಂತಿಗಳ ಬ್ರಹ್ಮಾಂಡವು ಎಣಿಸಬಹುದಾದ ಗುಂಪಾಗಿರುವುದರಿಂದ, ಪ್ರತಿ ಭಾಷೆಯನ್ನು ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳ ಒಂದು ವಿಶಿಷ್ಟ ಗುಂಪಿಗೆ ಮ್ಯಾಪ್ ಮಾಡಬಹುದು; ಹೀಗಾಗಿ, ಪ್ರತಿ ಭಾಷೆಯು ಏಕರೂಪದ ಆವೃತ್ತಿಯನ್ನು ಹೊಂದಿದೆ. ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ಪ್ರತಿ ಯೂನರಿ ಭಾಷೆಯು ಹೆಚ್ಚು ಸಾಂದ್ರವಾದ ಬೈನರಿ ಆವೃತ್ತಿಯನ್ನು ಹೊಂದಿದೆ, ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳ ಬೈನರಿ ಎನ್ಕೋಡಿಂಗ್ಗಳ ಸೆಟ್ k ಭಾಷೆಯಲ್ಲಿ 1k ಆಗಿದೆ. ಸಂಕೀರ್ಣತೆಯನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ನ ಉದ್ದದ ಆಧಾರದ ಮೇಲೆ ಅಳೆಯಲಾಗುತ್ತದೆಯಾದ್ದರಿಂದ, ಭಾಷೆಯ ಏಕರೂಪದ ಆವೃತ್ತಿಯು ಮೂಲ ಭಾಷೆಗಿಂತ "ಸುಲಭವಾಗಬಹುದು". ಉದಾಹರಣೆಗೆ, ಒಂದು ಭಾಷೆಯನ್ನು O (2n) ಸಮಯದಲ್ಲಿ ಗುರುತಿಸಬಹುದಾದರೆ, ಅದರ ಏಕರೂಪದ ಆವೃತ್ತಿಯನ್ನು O (n) ಸಮಯದಲ್ಲಿ ಗುರುತಿಸಬಹುದು, ಏಕೆಂದರೆ n ಘಾತೀಯವಾಗಿ ದೊಡ್ಡದಾಗಿದೆ. ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, ಒಂದು ಭಾಷೆಯನ್ನು ಓ (ಎಫ್ (ಎನ್)) ಸಮಯ ಮತ್ತು ಓ (ಜಿ (ಎನ್)) ಜಾಗದಲ್ಲಿ ಗುರುತಿಸಬಹುದಾದರೆ, ಅದರ ಏಕರೂಪದ ಆವೃತ್ತಿಯನ್ನು ಓ (ಎನ್ + ಎಫ್ (ಲಾಗ್ ಎನ್)) ಸಮಯ ಮತ್ತು ಓ (ಜಿ (ಲಾಗ್ ಎನ್)) ಜಾಗದಲ್ಲಿ ಗುರುತಿಸಬಹುದು (ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಓದಲು ನಮಗೆ ಓ (ಎನ್) ಸಮಯ ಬೇಕಾಗುತ್ತದೆ). ಆದಾಗ್ಯೂ, ಒಂದು ಭಾಷೆಯಲ್ಲಿ ಸದಸ್ಯತ್ವವು ಅನಿಶ್ಚಿತವಾಗಿದ್ದರೆ, ಅದರ ಏಕರೂಪದ ಆವೃತ್ತಿಯಲ್ಲಿ ಸದಸ್ಯತ್ವವು ಸಹ ಅನಿಶ್ಚಿತವಾಗಿದೆ. ಇತರ ಸಂಕೀರ್ಣತೆ ವರ್ಗಗಳೊಂದಿಗಿನ ಸಂಬಂಧಗಳು ಟಲ್ಲಿಯು ಪಿ/ಪಾಲಿಯಲ್ಲಿ ಒಳಗೊಂಡಿರುತ್ತದೆ-ಇನ್ಪುಟ್ ಉದ್ದವನ್ನು ಮಾತ್ರ ಅವಲಂಬಿಸಿರುವ ಸಲಹಾ ಕಾರ್ಯವನ್ನು ನೀಡಿದ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಗುರುತಿಸಬಹುದಾದ ಭಾಷೆಗಳ ವರ್ಗ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಅಗತ್ಯವಾದ ಸಲಹೆಯ ಕಾರ್ಯವು ತುಂಬಾ ಸರಳವಾಗಿದೆ-ಇದು 1k ಭಾಷೆಯಲ್ಲಿದೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸುವ ಪ್ರತಿ ಇನ್ಪುಟ್ ಉದ್ದ k ಗೆ ಒಂದೇ ಬಿಟ್ ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ಯುನರಿ ಭಾಷೆಯು ವಿರಳ ಭಾಷೆಯಾಗಿರಬೇಕು, ಏಕೆಂದರೆ ಪ್ರತಿ n ಗೆ ಇದು n ಉದ್ದದ ಗರಿಷ್ಠ ಒಂದು ಮೌಲ್ಯವನ್ನು ಮತ್ತು ಗರಿಷ್ಠ n ಉದ್ದದ ಗರಿಷ್ಠ n ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಆದರೆ ಎಲ್ಲಾ ವಿರಳ ಭಾಷೆಗಳು ಯುನರಿ ಅಲ್ಲ; ಆದ್ದರಿಂದ TALLY ಅನ್ನು SPARSE ನಲ್ಲಿ ಒಳಗೊಂಡಿದೆ. ಯಾವುದೇ ಎನ್ಪಿ-ಹಾರ್ಡ್ ಯುನಾರಿ ಭಾಷೆಗಳಿಲ್ಲ ಎಂದು ನಂಬಲಾಗಿದೆಃ ಎನ್ಪಿ-ಪೂರ್ಣವಾದ ಯುನಾರಿ ಭಾಷೆ ಇದ್ದರೆ, ಪಿ = ಎನ್ಪಿ. ಈ ಫಲಿತಾಂಶವನ್ನು ವಿರಳ ಭಾಷೆಗಳಿಗೆ ವಿಸ್ತರಿಸಬಹುದು. ಎಲ್ ಒಂದು ಏಕೀಕೃತ ಭಾಷೆಯಾಗಿದ್ದರೆ, ಎಲ್ * (ಎಲ್ ನ ಕ್ಲೈನ್ ಸ್ಟಾರ್) ಒಂದು ಸಾಮಾನ್ಯ ಭಾಷೆಯಾಗಿದೆ. ಸಂಕೀರ್ಣತೆ ವರ್ಗ ಪಿ1 ಎಂಬುದು ಬಹುಪದೀಯ ಸಮಯದ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಗುರುತಿಸಬಹುದಾದ ಯೂನರಿ ಭಾಷೆಗಳ ವರ್ಗವಾಗಿದೆ (ಅದರ ಇನ್ಪುಟ್ ಅನ್ನು ಯೂನರಿಯಲ್ಲಿ ಬರೆಯಲಾಗಿದೆ); ಇದು ಪಿ ವರ್ಗದ ಸಾದೃಶ್ಯವಾಗಿದೆ. ಎಣಿಕೆಯ ವರ್ಗವಾದ #P 1 ಅನ್ನು ಸಹ ಕರೆಯಲಾಗುತ್ತದೆ, ಇದು #P ನ ಸಾದೃಶ್ಯವಾಗಿದೆ. ಉಲ್ಲೇಖಗಳು ಸಾಮಾನ್ಯ ಉಲ್ಲೇಖಗಳು ಲ್ಯಾನ್ಸ್ ಫೋರ್ಟ್ನೋ. ನೆಚ್ಚಿನ ಪ್ರಮೇಯಗಳುಃ ಸಣ್ಣ ಸೆಟ್ಗಳು. ಏಪ್ರಿಲ್ 18,2006. http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html ಔಪಚಾರಿಕ ಭಾಷೆಗಳು ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತ