418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 8

อินพตุ:ประพจน์ที่มีตัวแปรไม่เกิน $n\,$ ตัว

เอาพุต:มีวิธีการกำหนดค่าตัวแปรให้ประพจน์เป็นจริงหรือไม่

แนวคิด ตัวแปรแต่ละตัวมีค่าได้สองค่า คือไม่จริงก็เท็จ การที่จะตรวจสอบว่า มีวิธีการกำหนดค่าตัวแปรให้ประพจน์เป็นจริงหรือไม่ต้องทำการลองกำหนดทุก ๆ แบบของตัวแปรที่เป็นไปได้ แต่ในห้องเรียน เราได้มีวิธีการสร้างซับเซตมาแล้ว และถ้าเราตีความใหม่ คือ ถ้า $g[i]=1\,$ หมายความว่า $x_{i}\,$ เป็นสมาชิกของซับเซต แต่ถ้า$g[i]=2\,$ หมายความว่า $x_{i}\,$ ไม่เป็นสมาชิกของซับเซต ดังนั้นเมื่อสร้างซับเซตได้แล้ว เราก็ทำการกำหนดว่า ถ้า $x_{i}\,$ เป็นสมาชิกของซับเซตให้ ตัวแปร $x_{i}\,$ มีค่าความจริงเป็นจริง ไม่เช่นนั้นให้มีค่าความจริงเป็นเท็จ หลังจากนั้นก็เอาวิธีการกำหนดค่าตัวแปรต่าง ๆ เหล่านี้ เรียกถาม subroutine (สมมติว่าชื่อ VERIFY เพื่อคำนวณหาค่าความจริงของประพจน์)

เวลาการทำงานของอัลกอริทึมข้างต้นก็จะเท่ากับเวลาการสร้างซับเซตทั้งหมด ซึ่งคือ$2^{n}\,$ และแต่ละซับเซตต้องเรียก VERIFY ซึ่งโจทย์กำหนดให้มีเวลาการทำงานเป็น M ดังนั้นเวลาการทำงานทั้งหมดของอัลกอริทึมคือ $O(2^{n}.M)\,$