لم تعویض

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

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

 منابع 






رده:نظریه پیچیدگی محاسباتی