لم تعویض

در نظریه پیچیدگی محاسباتی لم تعویض هوستاد یک ابزار کلیدی برای اثبات کران‌های پایین برای مدارهای بولی با عمق ثابت است. با استفاده از لم تعویض، یوهان هوستاد نشان داد که مدارهای بولی با عمق k که فقط در آن‌ها از گیت‌های منطقی AND,OR و NOT استفاده شده باشد برای محاسبهٔ تابع توازن نیازمند حداقل اندازهٔ

${\displaystyle \exp \left(\Omega \left(n^{\frac {1}{k-1}}\right)\right)}$

هستند. اثبات اولیه لم تعویض که توسط هوستاد ارائه شده بود نیازمند احتمالات شرطی بود. اما پس از آن اثبات ساده‌تری توسط (Razborov 1993) و (Beame 1994) ارائه داده شد.

منابع

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4, Zbl 1193.68112
• Beame, Paul (1994), "A Switching Lemma Primer", Manuscript
• Håstad, Johan (1987), Computational limitations of small depth circuits (PDF), Ph.D. thesis, Massachusetts Institute of Technology.
• Razborov, Alexander A. (1993), "An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic", Arithmetic, proof theory and computational complexity, 23: 247–277