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

ในด้านของ ทฤษฎีการคำนวณได้ และ ทฤษฎีความซับซ้อนในการคำนวณ คำว่า การลดรูป นั้นหมายถึงการพิจารณาการแก้ปัญหาอย่างหนึ่งให้ไปเป็นการแก้ปัญหาอีกปัญหาหนึ่ง ซึ่งบางทีอาจจะรู้สึกว่าปัญหานั้นไม่เกี่ยวกันเลยก็ได้ ถ้าเรากล่าวว่า "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) ซึ่งมีประโยชน์อย่างมากในการศึกษาทฤษฎีความซับซ้อนในการคำนวณเช่นกัน
นิยาม.
แม้ว่าการลดรูปที่เราใช้จะสามารถเป็นการลดรูปแบบใดก็ได้ แต่เพื่อความสะดวกในการนิยาม เราจะมาพิจารณาการลดรูปแบบที่ใช้เวลาเป็นฟังก์ชันพหุนามกับขนาดของอินพุตกัน
การลดรูปคุก.
เราจะกล่าวว่าปัญหา <math>\pi_1</math> ลดรูปแบบคุกไปเป็นปัญหา <math>\pi_2</math> เมื่อ มีขั้นตอนวิธี "A" ที่สามารถเรียกใช้ ออราเคิล <math>\pi_2</math> และ
 <math>\forall x \in \{0,1\}^*: x \in \pi_1 \iff A^{\pi_2} (x) =1 </math>
โดยที่ "A" ทำงานในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต
วิธีหนึ่งในการมองว่า A ลดรูปแบบคุกไปเป็น B ก็คือ การที่แก้ปัญหา A ได้อย่างมีประสิทธิภาพถ้าเรามี B เป็น subroutine แล้วเรียกใช้ได้ พิจารณาตัวอย่างของปัญหากลุ่มพรรคพวกดังนี้
การลดรูปคาร์ป.
เราจะกล่าวว่าปัญหา <math>\pi_1</math> ลดรูปแบบคาร์ปไปเป็นปัญหา <math>\pi_2</math> เมื่อมีฟังก์ชัน f ที่สามารถคำนวณได้ในเวลาที่เป็นพหุนามกับขนาดของอินพุต และ
 <math>\forall x \in \{0,1\}^* : x \in \pi_1 \iff f (x) \in \pi_2 </math>
การลดรูปคาร์ปค่อนข้างจะมีเงื่อนไขที่รุนแรงกว่าการลดรูปคุก (จะเห็นได้ชัดเจนว่า ถ้า A สามารถลดรูปคาร์ปเป็น B ได้ จะส่งผลให้ A สามารถลดรูปคุกเป็น B ได้เช่นกัน) การลดรูปคาร์ปนี้เป็นการลดรูปที่เหมาะสมที่สุดในการศึกษาปัญหาเอ็นพีบริบูรณ์ และเป็นที่นิยมในการนำมาสอนในชั้นเรียนปริญญาตรี ตัวอย่างของการลดรูปคาร์ปเช่น การลดรูปจากปัญหาความสอดคล้องแบบบูล (SAT) ไปเป็น ปัญหา 3-SAT อธิบายอย่างย่อได้ดังต่อไปนี้
การลดรูปเลวิน.
การลดรูปเลวินนี้ โดยมากแล้วจะไม่ค่อยได้เห็นกันเท่าไรนัก นิยามแบบเป็นทางการคือ เราจะกล่าวว่าปัญหา <math>\pi_1</math> สามารถลดรูปเลวินไปเป็นปัญหา <math>\pi_2</math> ได้ เมื่อมีฟังก์ชัน f g และ h ที่มีสมบัติคือ
สังเกตได้อย่างหนึ่งว่าการลดรูปเลวินส่งผลให้เกิดการลดรูปคาร์ปและคุกไปด้วย แต่มากไปกว่านั้นการลดรูปเลวินยังให้โอกาสในการแปลงบทพิสูจน์ระหว่างสองปัญหา โดย g ทำหน้าที่แปลงบทพิสูจน์ของ <math>\pi_1</math> ไปเป็น <math>\pi_2</math> ส่วน h ทำหน้าที่กลับกัน ส่วนนี้ของการลดรูปเลวินมีข้อดีคือ ถ้าเราพิสูจน์ได้ว่าปัญหาการตัดสินใจ A ลดรูปแบบเลวินไปเป็นปัญหาการตัดสินใจ B เราสามารถสรุปได้ทันทีว่าปัญหาการค้นหาคำตอบ (search problem) ของ A ลดรูปไปเป็นปัญหาการค้นหาคำตอบของ B ด้วย (เพราะว่าหลังจากเราแก้ปัญหา B และค้นหาบทพิสูจน์ (คำตอบ) ได้ เราสามารถใช้ h ในการแปลงบทพิสูจน์ของ B กลับไปเป็นบทพิสูจน์ของ A ได้)
พิจารณาตัวอย่าง ...