سیاوش یک چراغ جادو پیدا کرد که روی پیشانی غول آن عدد $0<e<1$ نوشته شده بود. بعد از تحقیق سیاوش فهمید که در صورتی که یک مسئله $SAT$ به این غول بدهد، غول تعداد جواب‌های درست آن را با تقریب $e$، با سرعت فراوان به او خواهد گفت. تقریب $e$‌ یعنی این‌که در صورتی که جواب مسئله $k$‌ باشد غول عددی بین $k+ke$ و $k-ke$ را به سیاوش تحویل می‌دهد.

سیاوش می‌خواهد با استفاده از این غول، غولی با عدد $\sigma$، به ازای هر $0 < \sigma < 1$ بسازد. با این شرط که تعداد استفاده از غول با عدد $e$ برای حداکثر ۱ بار باشد و الگوریتم او در زمان چند جمله‌ای بر حسب اندازه‌ی ورودی (یعنی مجموع اندازه‌ی جملات $SAT$) و $\frac{1}{\sigma }$ مسئله را حل کند.

توجه داشته باشید که $SAT$‌ مانند $SAT$-2 می‌باشد، فقط هر جمله‌ای از آن می‌تواند شامل چندین متغیر باشد.

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