TC (complexity)
ಸೈದ್ಧಾಂತಿಕ ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಮತ್ತು ನಿರ್ದಿಷ್ಟವಾಗಿ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತ ಮತ್ತು ಸರ್ಕ್ಯೂಟ್ ಸಂಕೀರ್ಣತೆ, ಟಿ. ಸಿ. ಯು ತೀರ್ಮಾನದ ಸಮಸ್ಯೆಗಳ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗವಾಗಿದ್ದು, ಇದನ್ನು ಮಿತಿ ಸರ್ಕ್ಯೂಟ್ಗಳಿಂದ ಗುರುತಿಸಬಹುದು, ಅವು ಎ. ಎನ್. ಡಿ., ಓ. ಆರ್. ಮತ್ತು ಮೆಜಾರಿಟಿ ಗೇಟ್ಗಳನ್ನು ಹೊಂದಿರುವ ಬೂಲಿಯನ್ ಸರ್ಕ್ಯೂಟ್ಗಳಾಗಿವೆ. ಪ್ರತಿ ಸ್ಥಿರ i ಗೆ, ಸಂಕೀರ್ಣತೆ ವರ್ಗ TCi ಆಳ, ಬಹುಪದ ಗಾತ್ರ ಮತ್ತು ಮಿತಿಯಿಲ್ಲದ ಫ್ಯಾನ್-ಇನ್ನ ಮಿತಿ ಸರ್ಕ್ಯೂಟ್ಗಳ ಕುಟುಂಬದಿಂದ ಗುರುತಿಸಬಹುದಾದ ಎಲ್ಲಾ ಭಾಷೆಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ವರ್ಗ TCಯನ್ನು NC ಮತ್ತು ACಯೊಂದಿಗಿನ ಸಂಬಂಧದ ಮೂಲಕ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ TC, NC ಮತ್ತು AC ಶ್ರೇಣಿಯ ನಡುವಿನ ಸಂಬಂಧವನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಸಂಕ್ಷಿಪ್ತಗೊಳಿಸಬಹುದುಃ ನಿರ್ದಿಷ್ಟವಾಗಿ, NC0 ಎಲ್ಲಾ ಇನ್ಪುಟ್ ಬಿಟ್ಗಳನ್ನು ಅವಲಂಬಿಸಿರುವ ಯಾವುದೇ ಕಾರ್ಯವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಸಾಧ್ಯವಿಲ್ಲ ಎಂಬ ಅಂಶದಿಂದ ಮೊದಲ ಕಟ್ಟುನಿಟ್ಟಾದ ನಿಯಂತ್ರಣವು ಅನುಸರಿಸುತ್ತದೆ ಎಂದು ನಮಗೆ ತಿಳಿದಿದೆ. ಹೀಗಾಗಿ ಎಸಿ0ನಲ್ಲಿ ಕ್ಷುಲ್ಲಕವಾಗಿರುವ ಮತ್ತು ಎಲ್ಲಾ ಬಿಟ್ಗಳ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿರುವ ಸಮಸ್ಯೆಯನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದರಿಂದ ಎರಡು ವರ್ಗಗಳನ್ನು ಬೇರ್ಪಡಿಸುತ್ತದೆ. (ಉದಾಹರಣೆಗೆ, OR ಕಾರ್ಯವನ್ನು ಪರಿಗಣಿಸಿ.) ಕಟ್ಟುನಿಟ್ಟಾದ ನಿಯಂತ್ರಣ ಎಸಿ0 ಟಿಸಿ0 ಅನುಸರಿಸುತ್ತದೆ ಏಕೆಂದರೆ ಪ್ಯಾರಿಟಿ ಮತ್ತು ಮೆಜಾರಿಟಿ (ಎರಡೂ ಟಿಸಿ0 ನಲ್ಲಿವೆ) ಎಸಿ0 ನಲ್ಲಿಲ್ಲ ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ಮೇಲಿನ ಪದಾರ್ಥಗಳ ತಕ್ಷಣದ ಪರಿಣಾಮವಾಗಿ, ನಾವು NC = AC = TC ಅನ್ನು ಹೊಂದಿದ್ದೇವೆ. ಉಲ್ಲೇಖಗಳು ಸರ್ಕ್ಯೂಟ್ ಸಂಕೀರ್ಣತೆ ಸಂಕೀರ್ಣತೆ ವರ್ಗಗಳು