====== $SAT$3 خوب ======
 


به هر عبارت منطقی که به صورت $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$ بیابید که این مسئله را حل کند.


<پاسخ>



</پاسخ>


  * [[سوال ۴|سوال بعد]]
  * [[سوال ۲|سوال قبل]]