TC (complexity)
نظریاتی کمپیوٹر سائنس میں، اور خاص طور پر کمپیوٹیشنل پیچیدگی کے نظریہ اور سرکٹ کی پیچیدگی، ٹی سی فیصلہ سازی کے مسائل کی ایک پیچیدگی کی کلاس ہے جسے تھریشولڈ سرکٹس کے ذریعے پہچانا جا سکتا ہے، جو کہ AND، OR، اور اکثریت کے دروازوں کے ساتھ بولین سرکٹس ہیں۔ ہر فکسڈ i کے لیے، پیچیدگی کی کلاس TCi ان تمام زبانوں پر مشتمل ہوتی ہے جنہیں گہرائی، کثیر الجہتی سائز، اور غیر محدود فین-ان کے حد سرکٹس کے خاندان کے ذریعے پہچانا جا سکتا ہے۔ کلاس ٹی سی کی تعریف این سی اور اے سی سے تعلق کے ذریعے کی گئی ہے۔ ٹی سی، این سی اور اے سی کے درجہ بندی کے درمیان تعلقات کا خلاصہ اس طرح کیا جا سکتا ہے: خاص طور پر، ہم جانتے ہیں کہ پہلی سخت روک تھام اس حقیقت سے ہوتی ہے کہ این سی 0 کسی بھی فنکشن کا حساب نہیں لگا سکتا جو تمام ان پٹ بٹس پر منحصر ہو۔ اس طرح کسی ایسے مسئلے کا انتخاب کرنا جو معمولی طور پر AC0 میں ہو اور تمام بٹس پر منحصر ہو، دونوں کلاسوں کو الگ کرتا ہے۔ (مثال کے طور پر، OR فنکشن پر غور کریں۔) سخت کنٹینمنٹ AC0 ′ TC0 کی پیروی کرتا ہے کیونکہ برابری اور اکثریت (جو دونوں TC0 میں ہیں) کو AC0 میں نہیں دکھایا گیا تھا۔ مندرجہ بالا کنٹینمنٹ کے فوری نتیجے کے طور پر، ہمارے پاس NC = AC = TC ہے۔ حوالہ جات سرکٹ پیچیدگی پیچیدگی کلاسیں