به هر عبارت منطقی که به صورت $OR$ دقیقا سه متغیر متفاوت به صورت $x_i$ یا $\overline{x_i}$ باشد، یک جمله سه‌تایی گفته می‌شود.

مسئله «$3SAT$ خوب» به این صورت تعریف می‌شود: تعدادی از جمله‌های سه‌تایی با یک‌دیگر $AND$ شده‌اند. می‌دانیم که هر متغیر $x_i$ در کل جمله‌ها، به صورت خود $x_i$ و یا نقیض آن $\overline{x_i}$ مجموعا روی هم حداکثر سه بار ظاهر شده است. می‌خواهیم به متغیر‌های $x_1,x_2,…,x_n$ طوری مقادیر $true$ یا $false$ نسبت بدهیم که کل عبارت مقدار $true$ داشته باشد.

الگوریتمی چند جمله‌ای بر حسب تعداد متغیر‌ها $n$ بیابید که این مسئله را حل کند.

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