تعقيد الدارات

تعقيد الدارات (الإنكليزية: Circuit complexity) هو أحد المواضيع المدروسة في نظرية التعقيد التحسيبي، أحد فروع علم الحاسوب النظري، والذي تصنف فيه التوابع المنطقية وفقاً لحجم موارد تحسيبية اللازمة لإنجازها. في تعقيد الدارات، هذه الموارد هي حجم وعمق الدارات المنطقية.

تعتبر كل دارة بدخل n بت عبارة عن مخطط حلقي موجه directed acyclic graph.

أصناف التعقيد المتصلة بالدارات المنطقية تضم AC⁰، AC، TC⁰ وNC.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 المصادر

• Ajtai, Miklós (1983). "$\Sigma _{1}^{1}$-formulae on finite structures". Annals of Pure and Applied Logic. 24: 1–24.
• Alon, Noga; Boppana, Ravi B. (1987). "The monotone circuit complexity of Boolean functions". Combinatorica. 7 (1): 1–22.
• Furst, Merrick L.; Saxe, James B.; Sipser, Michael (1984). "Parity, circuits, and the polynomial-time hierarchy". Mathematical Systems Theory. 17 (1): 13–27.
• Håstad, Johan (1987), Computational limitations of small depth circuits, Ph.D. thesis, Massachusetts Institute of Technology. 
• Hesse, William (2001). "Division is in uniform TC⁰". Proc. 28th International Colloquium on Automata, Languages and Programming: 104–114, Springer. 
• Raz, Ran; McKenzie, Pierre (1999). "Separation of the monotone NC hierarchy". Combinatorica. 19 (3): 403–435.
• Razborov, Alexander A. (1985). "Lower bounds on the monotone complexity of some Boolean functions". Mathematics of the USSR, Doklady. 31: 354–357.
• Shannon, Claude E. (1949). "The synthesis of two-terminal switching circuits". Bell System Technical Journal. 28 (1): 59–98.
• Smolensky, Roman (1987). "Algebraic methods in the theory of lower bounds for Boolean circuit complexity". Proc. 19th Annual ACM Symposium on Theory of Computing: 77–82, ACM. 
• Vollmer, Heribert (1999). Introduction to Circuit Complexity: a Uniform Approach. Springer Verlag. ISBN 3-540-64310-9.
• Wegener, Ingo (1987). The Complexity of Boolean Functions. John Wiley and Sons Ltd, and B. G. Teubner, Stuttgart. ISBN 3-519-02107-2. At the time an influental textbook on the subject, commonly known as the "Blue Book". Also available for download (PDF) at the Electronic Colloquium on Computational Complexity.
• Lecture notes for a course of Uri Zwick on circuit complexity
• Circuit Complexity before the Dawn of the New Millennium, a 1997 survey of the field by Eric Allender slides.