مسئله‌ی $SAT$ این‌گونه تعریف می‌شود: $n$‌متغیر $boolean$ داریم ( $x_1,...,x_n$ ) و یک تعدادی جمله. هر جمله عبارت‌است‌از یک یا چند متغیر ( $x_i$ یا $\bar x_i$ ). $\bar x_i$ مقدار عکس $x_i$ را دارد. مثلا $\{x_1,x_2,\bar x_4\}$ یک جمله است. مقدار یک جمله $TRUE$ می‌باشد، اگر و تنها اگر حداقل یکی از متغیر‌های آن $TRUE$ باشد. هدف مقدار دادن به همه‌ی متغیرهاست به نحوی که بیش‌ترین تعداد جملات مقدار $TRUE$ داشته باشند.

ما یک مسئله $SAT$ داریم. تنها نکته‌ی جالب آن، این است که اگر $m$ تا از این جملات وجود داشته باشند که نتوان به متغیرهای آن‌ها طوری مقدار داد که همه‌ی $m$ تا جمله مقدار $TRUE$ بگیرند، حتما $m>3$ است.

حالا ثابت کنید که یک روش مقداردهی برای متغیرهای این مسئله خوب وجود دارد که در آن حداقل $\frac{2}{3}$ از جملات $TRUE$ است.

• سوال بعد
• سوال قبل