لم تعویض

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

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

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

منابع

• الگو:Citation
• الگو:Citation
• الگو:Citation
• الگو:Citation