การลดรูป (ความซับซ้อน)

ในด้านของ ทฤษฎีการคำนวณได้ และ ทฤษฎีความซับซ้อนในการคำนวณ คำว่า การลดรูป นั้นหมายถึงการพิจารณาการแก้ปัญหาอย่างหนึ่งให้ไปเป็นการแก้ปัญหาอีกปัญหาหนึ่ง ซึ่งบางทีอาจจะรู้สึกว่าปัญหานั้นไม่เกี่ยวกันเลยก็ได้ ถ้าเรากล่าวว่า A ลดรูปเป็น B เราหมายความว่าการแก้ปัญหา B ได้จะส่งผลให้เราสามารถแก้ปัญหา A ได้ด้วย เพราะฉะนั้น A จะไม่ยากไปกว่า B การลดรูปในเชิงของทฤษฎีความซับซ้อนในการคำนวณนั้นมีมากมายหลายรูปแบบ แต่ละแบบจะนำมาใช้ในแง่ที่แตกต่างกัน แล้วแต่ว่าเรากำลังสนใจปัญหาแบบใด เช่นถ้าเราสนใจปัญหาของการนับ เราจะบอกว่าการนับจำนวนในเซ็ต A ลดรูปไปเป็นการนับจำนวนในเซ็ต B รูปแบบของการลดรูปที่เรานำมาใช้ก็ควรเป็นการลดรูปที่ไม่ทำให้จำนวนนั้นเปลี่ยนไป การลดรูปแบบนี้เรียกว่า (parsimonious reduction) การลดรูปที่มักจะใช้กันบ่อยๆก็คือ ทั้งสามแบบที่กล่าวมานี้เป็นการลดรูปแบบใช้เวลาเป็นพหุนามกับขนาดของอินพุต และถูกสร้างขึ้นมาเพื่อใช้นิยามความยากของเอ็นพี การลดรูปคุกจะมีลักษณะเหมือนกับการลดรูปทัวริง (Turing reduction) ในเชิงของทฤษฎีการคำนวณได้ (ที่ไม่สนใจว่าเวลาในการทำงานที่ใช้เป็นเท่าไร แต่จะเน้นที่การคำนวณได้เท่านั้น) การลดรูปคาร์ปจะเหมือนกับการลดรูปแบบเอ็ม (m-reduction or many-to-one reduction) การลดรูปทั้งสามแบบถูกจัดลำดับตามความรุนแรงของเงื่อนไขในการลดรูป (การลดรูปแบบเลวินมีเงื่อนไขที่รุนแรงที่สุด) แต่การลดรูปที่นักเรียนส่วนใหญ่ได้เรียนกันในชั้นเรียนคือ การลดรูปคุก และการลดรูปคาร์ป ซึ่งสามารถนำมาใช้ได้ง่ายกว่า และเพียงพอในการนำมาศึกษาเอ็นพีบริบูรณ์ นอกจากนี้ยังมีการลดรูปอีกแบบหนึ่งที่เป็นที่นิยมในหมู่ของ "นักทฤษฎีการคำนวณได้" (Computability Theorist) ก็คือ การลดรูปแบบตารางค่าความจริง (Truth table reduction or tt-reduction) ซึ่งมีระดับความรุนแรงของเงื่อนไขมากกว่าการลดรูปทัวริง แต่น้อยกว่าการลดรูปแบบเอ็ม แต่เราไม่ขอกล่าวถึงรายละเอียดในที่นี้ การลดรูปที่กล่าวมาทั้งหมดเป็นการลดรูปจากปัญหาหนึ่งไปอีกปัญหาหนึ่ง นอกจากนี้ยังมีการลดรูประหว่างปัญหาเดียวกันที่เรียกว่า การลดรูปตัวเอง (Self-reduction) และการลดรูปตัวเองแบบสุ่ม (Random self-reduction) ซึ่งมีประโยชน์อย่างมากในการศึกษาทฤษฎีความซับซ้อนในการคำนวณเช่นกัน แม้ว่าการลดรูปที่เราใช้จะสามารถเป็นการลดรูปแบบใดก็ได้ แต่เพื่อความสะดวกในการนิยาม เราจะมาพิจารณาการลดรูปแบบที่ใช้เวลาเป็นฟังก์ชันพหุนามกับขนาดของอินพุตกัน เราจะกล่าวว่าปัญหา 𝜋1 ลดรูปแบบคุกไปเป็นปัญหา 𝜋2 เมื่อ มีขั้นตอนวิธี A ที่สามารถเรียกใช้ ออราเคิล 𝜋2 และ โดยที่ A ทำงานในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต วิธีหนึ่งในการมองว่า A ลดรูปแบบคุกไปเป็น B ก็คือ การที่แก้ปัญหา A ได้อย่างมีประสิทธิภาพถ้าเรามี B เป็น subroutine แล้วเรียกใช้ได้ พิจารณาตัวอย่างของปัญหากลุ่มพรรคพวกดังนี้ เราจะกล่าวว่าปัญหา 𝜋1 ลดรูปแบบคาร์ปไปเป็นปัญหา 𝜋2 เมื่อมีฟังก์ชัน f ที่สามารถคำนวณได้ในเวลาที่เป็นพหุนามกับขนาดของอินพุต และ การลดรูปคาร์ปค่อนข้างจะมีเงื่อนไขที่รุนแรงกว่าการลดรูปคุก (จะเห็นได้ชัดเจนว่า ถ้า A สามารถลดรูปคาร์ปเป็น B ได้ จะส่งผลให้ A สามารถลดรูปคุกเป็น B ได้เช่นกัน) การลดรูปคาร์ปนี้เป็นการลดรูปที่เหมาะสมที่สุดในการศึกษาปัญหาเอ็นพีบริบูรณ์ และเป็นที่นิยมในการนำมาสอนในชั้นเรียนปริญญาตรี ตัวอย่างของการลดรูปคาร์ปเช่น การลดรูปจากปัญหาความสอดคล้องแบบบูล (SAT) ไปเป็น ปัญหา 3-SAT อธิบายอย่างย่อได้ดังต่อไปนี้ การลดรูปเลวินนี้ โดยมากแล้วจะไม่ค่อยได้เห็นกันเท่าไรนัก นิยามแบบเป็นทางการคือ เราจะกล่าวว่าปัญหา 𝜋1 สามารถลดรูปเลวินไปเป็นปัญหา 𝜋2 ได้ เมื่อมีฟังก์ชัน f g และ h ที่มีสมบัติคือ สังเกตได้อย่างหนึ่งว่าการลดรูปเลวินส่งผลให้เกิดการลดรูปคาร์ปและคุกไปด้วย แต่มากไปกว่านั้นการลดรูปเลวินยังให้โอกาสในการแปลงบทพิสูจน์ระหว่างสองปัญหา โดย g ทำหน้าที่แปลงบทพิสูจน์ของ 𝜋1 ไปเป็น 𝜋2 ส่วน h ทำหน้าที่กลับกัน ส่วนนี้ของการลดรูปเลวินมีข้อดีคือ ถ้าเราพิสูจน์ได้ว่าปัญหาการตัดสินใจ A ลดรูปแบบเลวินไปเป็นปัญหาการตัดสินใจ B เราสามารถสรุปได้ทันทีว่าปัญหาการค้นหาคำตอบ (search problem) ของ A ลดรูปไปเป็นปัญหาการค้นหาคำตอบของ B ด้วย (เพราะว่าหลังจากเราแก้ปัญหา B และค้นหาบทพิสูจน์ (คำตอบ) ได้ เราสามารถใช้ h ในการแปลงบทพิสูจน์ของ B กลับไปเป็นบทพิสูจน์ของ A ได้) พิจารณาตัวอย่าง ...