نمایش مبدأ برای لم تعویض

در [[نظریه پیچیدگی محاسباتی]] '''لم تعویض هوستاد''' یک ابزار کلیدی برای اثبات کران‌های پایین برای [[مدار بولی|مدارهای بولی]] با عمق ثابت است. با استفاده از لم تعویض، یوهان هوستاد نشان داد که [[مدار بولی|مدارهای بولی]] با عمق ''k'' که فقط در آن‌ها از[[دروازه منطقی| گیت‌های منطقی]] [[دروازه و|AND]],[[دروازه یا|OR]] و [[دروازه وارونگر|NOT]] استفاده شده باشد برای محاسبهٔ [[تابع هم‌ارزی|تابع توازن]] نیازمند حداقل اندازهٔ
: <math>\exp\left(\Omega\left(n^{\frac{1}{k-1}}\right)\right)</math>
هستند. اثبات اولیه لم تعویض که توسط هوستاد ارائه شده بود نیازمند [[احتمال شرطی|احتمالات شرطی]] بود. اما پس از آن اثبات ساده‌تری توسط {{Harvard citation text|Razborov|1993}} و {{Harvard citation text|Beame|1994}} ارائه داده شد.

== منابع ==
{{refbegin}}
* {{Citation|title=Computational Complexity: A Modern Approach|url=http://www.cs.princeton.edu/theory/complexity/|year=2009|ref=harv|last1=Arora|last2=Barak|first1=Sanjeev|first2=Boaz|authorlink1=Sanjeev Arora|publisher=[[Cambridge University Press|Cambridge]]|isbn=978-0-521-42426-4|zbl=1193.68112}}
* {{citation|last=Beame|first=Paul|title=A Switching Lemma Primer|year=1994|ref=harv|journal=Manuscript}}
* {{citation|last=Håstad|first=Johan|title=Computational limitations of small depth circuits|url=http://www.nada.kth.se/~johanh/thesis.pdf|year=1987|ref=harv|postscript=.|authorlink=Johan Håstad|publisher=Ph.D. thesis, Massachusetts Institute of Technology}}
* {{citation|last=Razborov|first=Alexander A.|title=An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic|year=1993|ref=harv|authorlink=Alexander Razborov|journal=Arithmetic, proof theory and computational complexity|volume=23|pages=247–277}}
{{refend}}{{علوم رایانه-خرد}}
[[رده:نظریه پیچیدگی محاسباتی]]