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

ในด้านของ ทฤษฎีการคำนวณได้ และ ทฤษฎีความซับซ้อนในการคำนวณ คำว่า การลดรูป นั้นหมายถึงการพิจารณาการแก้ปัญหาอย่างหนึ่งให้ไปเป็นการแก้ปัญหาอีกปัญหาหนึ่ง ซึ่งบางทีอาจจะรู้สึกว่าปัญหานั้นไม่เกี่ยวกันเลยก็ได้ ถ้าเรากล่าวว่า A ลดรูปเป็น B เราหมายความว่าการแก้ปัญหา B ได้จะส่งผลให้เราสามารถแก้ปัญหา A ได้ด้วย เพราะฉะนั้น A จะไม่ยากไปกว่า B

เกริ่นนำ

การลดรูปในเชิงของทฤษฎีความซับซ้อนในการคำนวณนั้นมีมากมายหลายรูปแบบ แต่ละแบบจะนำมาใช้ในแง่ที่แตกต่างกัน แล้วแต่ว่าเรากำลังสนใจปัญหาแบบใด เช่นถ้าเราสนใจปัญหาของการนับ เราจะบอกว่าการนับจำนวนในเซ็ต A ลดรูปไปเป็นการนับจำนวนในเซ็ต B รูปแบบของการลดรูปที่เรานำมาใช้ก็ควรเป็นการลดรูปที่ไม่ทำให้จำนวนนั้นเปลี่ยนไป การลดรูปแบบนี้เรียกว่า (parsimonious reduction) การลดรูปที่มักจะใช้กันบ่อยๆก็คือ

1. การลดรูปคุก (Cook reduction)
2. การลดรูปคาร์ป (Karp reduction)
3. การลดรูปเลวิน (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 ได้)

พิจารณาตัวอย่าง ...