مدار
در این مسئله با تعدادی گیت سر و کار داریم. هر گیت یک یا چند ورودی و یک خروجی دارد. ورودی و خروجی یک گیت فقط مقادیر ۰ و ۱ است. سه نوع گیت $or،not$ و $and$ در اختیار داریم.
- گیت $and$ دو ورودی و یک خروجی دارد. خروجی آن ۱ است اگر و تنها اگر هر دو ورودی آن ۱ باشند.
- گیت $or$ دو ورودی و یک خروجی دارد. خروجی آن ۰ است اگر و تنها اگر هر دو ورودی آن ۰ باشد.
- گیت $not$ یک ورودی و یک خروجی دارد. اگر ورودی آن ۱ باشد، خروجی آن ۰ و اگر ورودی آن ۰ باشد خروجی آن ۱ است.
- یک مدار شامل تعدادی گیت است که ورودی‌ها و خروجی‌های آن‌ها به هم متصل شده است!
مثلا شکل زیر یک مدار است.
- در یک جعبه اندازه‌ی کافی گیت $and$ داریم. می‌دانیم حداکثر $k$ تا از این گیت‌ها خراب شده‌اند و مثل گیت $or$ عمل می‌کنند ($k$ یک عدد ثابت است). مداری طراحی کنید که کار گیت $and$ را انجام دهد. مدار شما باید دارای ۲ ورودی و ۱ خروجی باشد. به جز این دو ورودی هیچ مقدار دیگری در اختیار نداریم مگر اینکه با گیت‌های موجود در جعبه ساخته شود.
- در یک جعبه به اندازه‌ی کافی گیت از هر سه نوع داریم. هر گیت برچسب مخصوص به خود را دارد. یعنی گیت‌ها ازهم متمایزند. حداکثر $k$ تا ا ز گیت‌ها خراب هستند و خروجی آن‌ها یکی از ورودی‌های آن‌ها به دل‌خواه است. مداری طراحی کنید که کار گیت $not$ را انجام دهد. توجه کنید که در هر دو قسمت این مسئله نمی‌دانیم کدام گیت‌ها خراب هستند!