ภาวะลดทอนได้และระดับของภาวะแก้ไม่ได้

ภาวะลดทอนได้ (reducibility) เปรียบเทียบความยากของปัญหาโดยการแปลงปัญหาหนึ่งไปเป็นอีกปัญหาหนึ่ง และการจัดกลุ่มปัญหาที่มีความยากเท่ากันจะทำให้เกิดระดับของภาวะแก้ไม่ได้ (degrees of unsolvability) ซึ่งเป็นโครงสร้างของโลกที่อยู่นอกเหนือขีดความสามารถในการคำนวณ

Definition

ปัญหาหนึ่งจะลดทอนได้ไปเป็นอีกปัญหาหนึ่งเมื่ออัลกอริทึมที่สามารถเข้าถึงตัวแก้สำหรับปัญหาที่สองสามารถแก้ปัญหาแรกได้ ปัญหาที่ลดทอนซึ่งกันและกันจะมีความยากในการแก้ปัญหาในระดับเดียวกัน และระดับเหล่านี้จะก่อตัวเป็นลำดับที่ใช้วัดความยากเชิงอัลกอริทึมสัมพัทธ์

Scope

หัวข้อนี้ครอบคลุมถึงภาวะลดทอนได้แบบหลายต่อหนึ่ง (many-one reducibility) และแบบทัวริง (Turing reducibility) การใช้การลดทอนเพื่อพิสูจน์ภาวะตัดสินใจไม่ได้ (undecidability) การดำเนินการกระโดดแบบทัวริง (Turing jump operation) ที่สร้างปัญหาที่ยากขึ้นอย่างเคร่งครัด ลำดับชั้นทางคณิตศาสตร์ (arithmetical hierarchy) ที่จำแนกปัญหาตามความซับซ้อนเชิงตรรกะ และผลลัพธ์หลักของทฤษฎีระดับขั้น (degree theory) เช่น การมีอยู่ของระดับขั้นกลาง (intermediate degrees)

Core questions

• เราจะกล่าวได้อย่างไรว่าปัญหาที่แก้ไม่ได้ปัญหาหนึ่งยากกว่าอีกปัญหาหนึ่ง?
• การลดทอนถูกนำมาใช้ทั้งในการพิสูจน์ภาวะตัดสินใจไม่ได้และในการจัดระเบียบปัญหาได้อย่างไร?
• การกระโดดแบบทัวริงสร้างอะไรขึ้นมา และเหตุใดจึงยากขึ้นอย่างเคร่งครัดเสมอ?
• มีปัญหาที่อยู่ระหว่างปัญหาที่ตัดสินใจได้ (decidable) และปัญหาการหยุดทำงาน (halting problem) อย่างเคร่งครัดหรือไม่?

Key theories

ภาวะลดทอนได้และการกระโดดแบบทัวริง

ภาวะลดทอนได้แบบทัวริงเชื่อมโยงปัญหาต่างๆ โดยการคำนวณแบบโอราเคิล และการกระโดดของปัญหา ซึ่งเข้ารหัสการหยุดทำงานที่สัมพันธ์กับปัญหานั้น จะยากกว่าเสมออย่างเคร่งครัด ทำให้เกิดหอคอยที่ไม่มีที่สิ้นสุดของปัญหาที่ยากขึ้นเรื่อยๆ

การมีอยู่ของระดับขั้นกลาง

ทฤษฎีบทฟรีดเบิร์ก-มัชนิกได้แก้ปัญหาของโพสต์โดยการสร้างปัญหาที่สามารถคำนวณได้ซึ่งไม่สามารถตัดสินใจได้ แต่ยังคงง่ายกว่าปัญหาการหยุดทำงานอย่างเคร่งครัด โดยใช้วิธีการจัดลำดับความสำคัญ ซึ่งแสดงให้เห็นว่าระดับขั้นต่างๆ มีโครงสร้างที่ซับซ้อน

Clinical relevance

เทคนิคการลดทอนเป็นเครื่องมือที่ใช้ในชีวิตประจำวันสำหรับการพิสูจน์ว่าปัญหาไม่สามารถแก้ไขได้ หรือในทฤษฎีความซับซ้อน (complexity theory) คือการพิสูจน์ว่าปัญหาไม่สามารถจัดการได้ (intractable): การแสดงให้เห็นว่าปัญหาที่ทราบว่ายากสามารถลดทอนไปสู่ปัญหาใหม่ได้ จะเป็นการถ่ายทอดความยากนั้น ซึ่งเป็นวิธีการที่ใช้ในการสร้างผลลัพธ์เกี่ยวกับภาวะตัดสินใจไม่ได้และ NP-สมบูรณ์ (NP-completeness) ทั่วทั้งคณิตศาสตร์และวิทยาการคอมพิวเตอร์

History

ทัวริงได้นำเสนอเครื่องจักรโอราเคิล (oracle machines) ในปี 1939 และโพสต์ในปี 1944 ได้กำหนดกรอบการศึกษาเกี่ยวกับระดับของภาวะแก้ไม่ได้ และตั้งคำถามว่ามีระดับของภาวะแก้ไม่ได้ที่สามารถคำนวณได้ (computably enumerable degrees) ระดับกลางหรือไม่ ฟรีดเบิร์กและมัชนิกได้แก้ไขปัญหานี้อย่างอิสระในปี 1956–1957 โดยการประดิษฐ์วิธีการจัดลำดับความสำคัญ (priority method) ซึ่งกลายเป็นเทคนิคหลักของสาขาวิชานี้

Key figures

• Emil Post
• Alan Turing
• Richard Friedberg
• Albert Muchnik

Seminal works

• soare2016
• rogers1987

Frequently asked questions

การลดทอนคืออะไร ในเชิงแนวคิด?

เป็นการแก้ปัญหาหนึ่งโดยใช้ตัวแก้สำหรับอีกปัญหาหนึ่ง หากคุณสามารถแปลอินสแตนซ์ใดๆ ของปัญหา A ไปเป็นอินสแตนซ์ของปัญหา B เพื่อให้คำตอบตรงกันได้ แสดงว่า B ยากกว่า A อย่างน้อย และการแก้ปัญหา B จะนำไปสู่การแก้ปัญหา A

มีปัญหาที่ยากกว่าปัญหาการหยุดทำงานหรือไม่?

มีจำนวนไม่สิ้นสุด การประยุกต์ใช้การกระโดดแบบทัวริงกับปัญหาการหยุดทำงานจะให้ปัญหาที่ยากขึ้นอย่างเคร่งครัด และการทำซ้ำการดำเนินการนี้จะสร้างลำดับชั้นที่ไม่มีที่สิ้นสุด ดังนั้นภาวะแก้ไม่ได้จึงมีระดับขั้นที่ไม่จำกัด แทนที่จะเป็นเพียงระดับเดียว