جلسه‌ی بیست و چهارم

در سال ۱۹۸۶ لمی با مضمون لم جداکننده ارائه می‌شود که در زمینه پیچیدگی محاسباتی به نوبه خود نتایجی هیجان انگیز در بر داشت. گزاره این لم که اثبات ساده‌ای دارد بدین شکل است: «فرض کنید E یک مجموعه و B خانواده‌ای از زیرمجموعه‌های E باشد. اگر به عناصر E وزنی تصادفی از اعداد 1 تا 2×|E| نسبت دهیم، با احتمال حداقل یک دوم، عضوی از B که کمینه وزن را اتخاذ می‌کند یکتا است».
در این ارائه به بررسی مقاله «matching is as easy as matrix inversion» نوشته Mulmuley و برادران Vazirani می‌پردازیم. در آن پس از اثبات لم، الگوریتمی تصادفی و موازی برای یافتن بیشینه تطابق ارائه می‌شود.
به امید آنکه روزی وقت یاری دهد تا قضیه Toda که در مقاله «PP is as hard as the polynomial-time hierarchy» آمده است را مطالعه و ارائه دهم. این قضیه که برنده جایه گودل ۱۹۹۸ بوده است، از لم جداکننده مذکور استفاده می‌کند. همانطور که از اسم مقاله مشخص است، بیان می‌کند که PH⊆P^{PP}.