ปัญหาความสอดคล้องแบบบูล

จากวิกิพีเดีย สารานุกรมเสรี

บทความนี้มีลิงก์แทรกในบทความที่ข้ามไปภาษาอื่นโดยเป็นลิงก์สีฟ้าอ่อน โดยผู้เขียนใส่ไว้เพื่อสะดวกในการเขียน และควรแก้ลิงก์ภาษาอื่นเป็นข้อความธรรมดา เมื่อมีลิงก์ภาษาไทยที่ถูกต้อง หรือเห็นควร เพื่อไม่ให้ผู้อ่านสับสน

ปัญหาความสอดคล้องแบบบูล (Boolean satisfiability) หรือ SAT เป็น ปัญหาการตัดสินใจ อย่างหนึ่งที่ถูกกล่าวถึงบ่อยๆในศาสตร์ทางด้านทฤษฎีความซับซ้อนในการคำนวณ ตัวอย่างของปัญหา (instance) สำหรับปัญหานี้ก็คือ นิพจน์บูลีน (boolean expression) ที่ประกอบด้วยตัวแปร ตัวเชื่อมต่างๆ และ วงเล็บ ปัญหานี้ถามคำถามที่ว่า สำหรับนิพจน์บูลีนที่กำหนด เราสามารถทำให้นิพจน์เป็นจริงโดยการกำหนดค่าให้กับตัวแปรได้หรือไม่

ในกรณีที่เราสามารถกำหนดค่าความจริงให้กับตัวแปรแล้วทำให้นิพจน์เป็นจริงได้ เราจะกล่าวว่านิพจน์นั้น สามารถทำให้เป็นจริงได้ (satisfiable) ปัญหา SAT จัดอยู่ในกลุ่มของปัญหาเอ็นพีบริบูรณ์ (NP-complete)

ในบางครั้งเราอาจจะสนใจศีกษาความซับซ้อนของรูปแบบที่ต่างกันออกไปของปัญหา SAT ยกตัวอย่างเช่นปัญหา SAT แบบที่นิพจน์บูลีนอยู่ในรูปมาตรฐานแบบเชื่อม (หรือ Conjunctive Normal Form---CNF) ในกรณีนี้ถ้าแต่ละประพจน์เลือก (disjunct) ประกอบด้วยตัวแปรไม่เกิน 3 ตัวแปรเราจะเรียกปัญหาว่า 3-SAT ซึ่งเป็นปัญหาเอ็นพีบริบูรณ์เช่นเดียวกัน อย่างไรก็ตาม ในกรณีที่ตัวแปรในแต่ละประพจน์เลือกมีไม่เกิน 2 ตัวแปร (เรียกว่าปัญหา 2-SAT) นั้น เรามีอัลกอริธึมที่มีประสิทธิภาพในการแก้ปัญหาได้ นั่นก็คือ หรือหากจะพูดให้ชัดเจนกว่านั้น (ทั้งนี้เนื่องจากอัลกอริทึมที่ใช้แก้ปัญหา 2-SAT เป็นอัลกอริทึมที่ทำงานโดยใช้เนื้อที่เป็นลอการิธึมบนเครื่องจักรทัวริงเชิงไม่กำหนดเท่านั้น)

[แก้] ความยากของปัญหา

[แก้] อัลกอริทึมที่ใช้สำหรับปัญหา

[แก้] อ้างอิง