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

ในด้านของ ทฤษฎีการคำนวณได้ และ ทฤษฎีความซับซ้อนในการคำนวณ คำว่า การลดรูป นั้นหมายถึงการพิจารณาการแก้ปัญหาอย่างหนึ่งให้ไปเป็นการแก้ปัญหาอีกปัญหาหนึ่ง ซึ่งบางทีอาจจะรู้สึกว่าปัญหานั้นไม่เกี่ยวกันเลยก็ได้ ถ้าเรากล่าวว่า A ลดรูปเป็น B เราหมายความว่าการแก้ปัญหา B ได้จะส่งผลให้เราสามารถแก้ปัญหา A ได้ด้วย เพราะฉะนั้น A จะไม่ยากไปกว่า B
== เกริ่นนำ ==
การลดรูปในเชิงของทฤษฎีความซับซ้อนในการคำนวณนั้นมีมากมายหลายรูปแบบ แต่ละแบบจะนำมาใช้ในแง่ที่แตกต่างกัน แล้วแต่ว่าเรากำลังสนใจปัญหาแบบใด เช่นถ้าเราสนใจปัญหาของการนับ เราจะบอกว่าการนับจำนวนในเซ็ต A ลดรูปไปเป็นการนับจำนวนในเซ็ต B รูปแบบของการลดรูปที่เรานำมาใช้ก็ควรเป็นการลดรูปที่ไม่ทำให้จำนวนนั้นเปลี่ยนไป การลดรูปแบบนี้เรียกว่า (parsimonious reduction) การลดรูปที่มักจะใช้กันบ่อยๆก็คือ
การลดรูปคุก (Cook reduction)
การลดรูปคาร์ป (Karp reduction)
การลดรูปเลวิน (Levin reduction)
ทั้งสามแบบที่กล่าวมานี้เป็นการลดรูปแบบใช้เวลาเป็นพหุนามกับขนาดของอินพุต และถูกสร้างขึ้นมาเพื่อใช้นิยามความยากของเอ็นพี การลดรูปคุกจะมีลักษณะเหมือนกับการลดรูปทัวริง (Turing reduction) ในเชิงของทฤษฎีการคำนวณได้ (ที่ไม่สนใจว่าเวลาในการทำงานที่ใช้เป็นเท่าไร แต่จะเน้นที่การคำนวณได้เท่านั้น) การลดรูปคาร์ปจะเหมือนกับการลดรูปแบบเอ็ม (m-reduction or many-to-one reduction)
การลดรูปทั้งสามแบบถูกจัดลำดับตามความรุนแรงของเงื่อนไขในการลดรูป (การลดรูปแบบเลวินมีเงื่อนไขที่รุนแรงที่สุด) แต่การลดรูปที่นักเรียนส่วนใหญ่ได้เรียนกันในชั้นเรียนคือ การลดรูปคุก และการลดรูปคาร์ป ซึ่งสามารถนำมาใช้ได้ง่ายกว่า และเพียงพอในการนำมาศึกษาเอ็นพีบริบูรณ์ นอกจากนี้ยังมีการลดรูปอีกแบบหนึ่งที่เป็นที่นิยมในหมู่ของ "นักทฤษฎีการคำนวณได้" (Computability Theorist) ก็คือ การลดรูปแบบตารางค่าความจริง (Truth table reduction or tt-reduction) ซึ่งมีระดับความรุนแรงของเงื่อนไขมากกว่าการลดรูปทัวริง แต่น้อยกว่าการลดรูปแบบเอ็ม แต่เราไม่ขอกล่าวถึงรายละเอียดในที่นี้
การลดรูปที่กล่าวมาทั้งหมดเป็นการลดรูปจากปัญหาหนึ่งไปอีกปัญหาหนึ่ง นอกจากนี้ยังมีการลดรูประหว่างปัญหาเดียวกันที่เรียกว่า การลดรูปตัวเอง (Self-reduction) และการลดรูปตัวเองแบบสุ่ม (Random self-reduction) ซึ่งมีประโยชน์อย่างมากในการศึกษาทฤษฎีความซับซ้อนในการคำนวณเช่นกัน
== นิยาม ==
แม้ว่าการลดรูปที่เราใช้จะสามารถเป็นการลดรูปแบบใดก็ได้ แต่เพื่อความสะดวกในการนิยาม เราจะมาพิจารณาการลดรูปแบบที่ใช้เวลาเป็นฟังก์ชันพหุนามกับขนาดของอินพุตกัน
=== การลดรูปคุก ===
เราจะกล่าวว่าปัญหา \pi_1 ลดรูปแบบคุกไปเป็นปัญหา \pi_2 เมื่อ มีขั้นตอนวิธี A ที่สามารถเรียกใช้ ออราเคิล \pi_2 และ
\forall x \in \{0,1\}^*: x \in \pi_1 \iff A^{\pi_2} (x) =1 
โดยที่ A ทำงานในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต
วิธีหนึ่งในการมองว่า A ลดรูปแบบคุกไปเป็น B ก็คือ การที่แก้ปัญหา A ได้อย่างมีประสิทธิภาพถ้าเรามี B เป็น subroutine แล้วเรียกใช้ได้ พิจารณาตัวอย่างของปัญหากลุ่มพรรคพวกดังนี้
=== การลดรูปคาร์ป ===
เราจะกล่าวว่าปัญหา \pi_1 ลดรูปแบบคาร์ปไปเป็นปัญหา \pi_2 เมื่อมีฟังก์ชัน f ที่สามารถคำนวณได้ในเวลาที่เป็นพหุนามกับขนาดของอินพุต และ
\forall x \in \{0,1\}^* : x \in \pi_1 \iff f (x) \in \pi_2 
การลดรูปคาร์ปค่อนข้างจะมีเงื่อนไขที่รุนแรงกว่าการลดรูปคุก (จะเห็นได้ชัดเจนว่า ถ้า A สามารถลดรูปคาร์ปเป็น B ได้ จะส่งผลให้ A สามารถลดรูปคุกเป็น B ได้เช่นกัน) การลดรูปคาร์ปนี้เป็นการลดรูปที่เหมาะสมที่สุดในการศึกษาปัญหาเอ็นพีบริบูรณ์ และเป็นที่นิยมในการนำมาสอนในชั้นเรียนปริญญาตรี ตัวอย่างของการลดรูปคาร์ปเช่น การลดรูปจากปัญหาความสอดคล้องแบบบูล (SAT) ไปเป็น ปัญหา 3-SAT อธิบายอย่างย่อได้ดังต่อไปนี้
=== การลดรูปเลวิน ===
การลดรูปเลวินนี้ โดยมากแล้วจะไม่ค่อยได้เห็นกันเท่าไรนัก นิยามแบบเป็นทางการคือ เราจะกล่าวว่าปัญหา \pi_1 สามารถลดรูปเลวินไปเป็นปัญหา \pi_2 ได้ เมื่อมีฟังก์ชัน f g และ h ที่มีสมบัติคือ
x \in \pi_1 \iff f (x) \in \pi_2
สำหรับทุก x,y ถ้า y เป็นบทพิสูจน์ของ x ในปัญหา \pi_1 แล้ว g (x,y) จะเป็นบทพิสูจน์ของ f (x) ใน \pi_2
สำหรับทุก x,z ถ้า z เป็นบทพิสูจน์ของ f (x) ในปัญหา \pi_2 แล้ว h (x,z) จะเป็นบทพิสูจน์ของ x ใน \pi_1
สังเกตได้อย่างหนึ่งว่าการลดรูปเลวินส่งผลให้เกิดการลดรูปคาร์ปและคุกไปด้วย แต่มากไปกว่านั้นการลดรูปเลวินยังให้โอกาสในการแปลงบทพิสูจน์ระหว่างสองปัญหา โดย g ทำหน้าที่แปลงบทพิสูจน์ของ \pi_1 ไปเป็น \pi_2 ส่วน h ทำหน้าที่กลับกัน ส่วนนี้ของการลดรูปเลวินมีข้อดีคือ ถ้าเราพิสูจน์ได้ว่าปัญหาการตัดสินใจ A ลดรูปแบบเลวินไปเป็นปัญหาการตัดสินใจ B เราสามารถสรุปได้ทันทีว่าปัญหาการค้นหาคำตอบ (search problem) ของ A ลดรูปไปเป็นปัญหาการค้นหาคำตอบของ B ด้วย (เพราะว่าหลังจากเราแก้ปัญหา B และค้นหาบทพิสูจน์ (คำตอบ) ได้ เราสามารถใช้ h ในการแปลงบทพิสูจน์ของ B กลับไปเป็นบทพิสูจน์ของ A ได้)
พิจารณาตัวอย่าง ...
== ประโยชน์ของการลดรูป ==
== การลดรูปแบบอื่นๆ ==
ทฤษฎีความซับซ้อนในการคำนวณ