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

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

ในด้านของ ทฤษฎีการคำนวณได้ และ ทฤษฎีความซับซ้อนในการคำนวณ คำว่า การลดรูป นั้นหมายถึงการพิจารณาการแก้ปัญหาอย่างหนึ่งให้ไปเป็นการแก้ปัญหาอีกปัญหาหนึ่ง ซึ่งบางทีอาจจะรู้สึกว่าปัญหานั้นไม่เกี่ยวกันเลยก็ได้ ถ้าเรากล่าวว่า 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 ได้)

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

ประโยชน์ของการลดรูป[แก้]

การลดรูปแบบอื่นๆ[แก้]