طراحی و تحلیل الگوریتم‌ها در مهندسی کامپیوتر: مسئله 3-SAT - کوییز

1. 3-SAT زیرمجموعه ای از SAT است که در آن هر بند (clause) حداکثر 3 متغیر دارد.
2. 3-SAT زیرمجموعه ای از SAT است که در آن هر بند دقیقاً 3 متغیر دارد.
3. SAT زیرمجموعه ای از 3-SAT است که در آن هر بند حداکثر 3 متغیر دارد.
4. 3-SAT و SAT دو مسئله کاملاً مجزا در حوزه رضایت پذیری هستند.

گزینه صحیح: 2

توضیح: مسئله 3-SAT حالتی خاص از مسئله رضایت پذیری (SAT) است که در آن فرمول بولی به صورت بند نرمال عطفی (Conjunctive Normal Form - CNF) بیان می شود و هر بند دقیقاً شامل سه لیترال (literal) است.

1. Vertex Cover مسئله ای ساده تر از 3-SAT است.
2. Vertex Cover مسئله ای NP-hard است.
3. Vertex Cover مسئله ای در کلاس P است.
4. Vertex Cover مسئله ای در کلاس BQP است.

گزینه صحیح: 2

توضیح: کاهش مسئله Vertex Cover به 3-SAT یکی از اثبات های اساسی برای NP-hardness مسئله 3-SAT است. این کاهش نشان می دهد که اگر Vertex Cover قابل حل در زمان چندجمله ای باشد، 3-SAT نیز قابل حل خواهد بود.

1. الگوریتم DPLL
2. الگوریتم Guruswami-Sudan
3. الگوریتم WalkSAT
4. الگوریتم Edmonds-Karp

گزینه صحیح: 1

توضیح: الگوریتم DPLL (Davis-Putnam-Logemann-Loveland) یک الگوریتم مبتنی بر عقب گرد (backtracking) است که برای حل مسائل SAT استفاده می شود. در بد ترین حالت، پیچیدگی زمانی آن نمایی است، که نشان دهنده NP-completeness مسئله است.

1. (x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ ¬x3)
2. (x1 ∨ x2) ∧ (¬x1 ∨ x3 ∨ x4)
3. (¬x1 ∨ ¬x2 ∨ ¬x3) ∧ (x1 ∨ x2 ∨ x3)
4. (x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ ¬x3)

گزینه صحیح: 2

توضیح: مسئله 3-SAT نیازمند این است که هر بند دقیقاً سه لیترال داشته باشد. گزینه دوم دارای بندی با دو لیترال (x1 ∨ x2) و بندی با چهار لیترال (¬x1 ∨ x3 ∨ x4) است که آن را از تعریف 3-SAT خارج می کند.

1. ساخت یک فرمول 3-SAT که متناظر با یک تطابق 3 بعدی باشد.
2. ساخت یک مسئله 3-SAT که پیچیدگی آن کمتر از 3-Dimensional Matching باشد.
3. نشان دادن اینکه 3-Dimensional Matching یک مسئله P است.
4. استفاده از الگوریتم های تقریبی برای حل 3-Dimensional Matching.

گزینه صحیح: 1

توضیح: اثبات NP-completeness 3-SAT از طریق کاهش از 3-Dimensional Matching، با ساخت یک فرمول 3-SAT به گونه ای انجام می شود که وجود یک حل برای مسئله 3-Dimensional Matching معادل با وجود یک تخصیص متغیر (satisfying assignment) برای فرمول 3-SAT حاصل باشد.

1. الگوریتم های تقریبی (Approximation Algorithms)
2. الگوریتم های تصادفی (Randomized Algorithms) مانند WalkSAT
3. الگوریتم های قطعی با پیچیدگی زمانی نمایی
4. الگوریتم های کوانتومی

گزینه صحیح: 2

توضیح: الگوریتم های تصادفی مانند WalkSAT و GSAT، با وجود اینکه تضمین حل در بد ترین حالت را ندارند، در عمل برای فرمول های بزرگ 3-SAT عملکرد بسیار خوبی از خود نشان داده اند و اغلب سریعتر از الگوریتم های قطعی عمل می کنند.

1. زیرا پایه و اساس اثبات NP-completeness بسیاری از مسائل دیگر است.
2. زیرا الگوریتم های حل آن همیشه در زمان چندجمله ای اجرا می شوند.
3. زیرا این مسئله تن ها مسئله NP-complete شناخته شده است.
4. زیرا حل آن مستقیماً منجر به حل مسائل P می شود.

گزینه صحیح: 1

توضیح: مسئله 3-SAT به دلیل اینکه اولین مسئله ای بود که NP-complete بودن آن اثبات شد (از طریق کاهش از مسئله P) و هم چنین به دلیل اینکه بسیاری از مسائل دیگر NP-complete از طریق کاهش به آن اثبات شده اند، اهمیت تئوریک فوق العاده ای دارد.