ในทฤษฎีความสามารถในการคำนวณ มี การศึกษา ความสัมพันธ์ในการลดรูป (หรือเรียกว่าการลดรูปความสามารถในการลดรูปและแนวคิดเรื่องความสามารถในการลดรูป ) มากมายแรงจูงใจในการศึกษามาจากคำถามที่ว่า: เมื่อกำหนดเซตและของจำนวนธรรมชาติแล้ว เป็นไปได้หรือไม่ที่จะแปลงวิธีการตัดสินสมาชิกภาพใน ไปเป็นวิธีการตัดสินสมาชิกภาพในได้อย่างมีประสิทธิภาพ ? ถ้าคำตอบของคำถามนี้คือใช่ ก็จะกล่าวได้ว่า สามารถ ลดรูป ไปเป็นได้ ${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$

การศึกษาแนวคิดเรื่องการลดรูปได้นั้นได้รับแรงบันดาลใจจากการศึกษาปัญหาการตัดสินใจสำหรับแนวคิดเรื่องการลดรูปได้หลายๆ แนวคิด หาก เซต ที่ไม่สามารถคำนวณได้ ใดๆ สามารถลดรูปได้เป็นเซตอื่น เซตนั้นก็ต้องไม่สามารถคำนวณได้เช่นกัน นี่เป็นเทคนิคที่มีประสิทธิภาพในการพิสูจน์ว่าเซตจำนวนมากไม่สามารถคำนวณได้ ${\displaystyle A}$${\displaystyle A}$

ความสัมพันธ์แบบลดรูปได้ (Reducibility relation ) คือความสัมพันธ์ทวิภาคบนเซตของจำนวนธรรมชาติ ซึ่งก็คือ

• สมบัติสะท้อนกลับ : ทุกเซตสามารถลดทอนเหลือตัวมันเองได้
• คุณสมบัติถ่ายทอด : ถ้าเซตหนึ่งสามารถลดรูปได้เป็นเซตหนึ่งและเซตหนึ่งสามารถลดรูปได้เป็นเซตอีกเซตหนึ่งแล้วเซตนั้นก็สามารถลดรูปได้เป็นเซตอีกเซตหนึ่งเช่นกัน${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle C}$${\displaystyle A}$${\displaystyle C}$

คุณสมบัติทั้งสองนี้บ่งชี้ว่าความสามารถในการลดรูปได้เป็นลำดับเบื้องต้นบนเซตกำลังของจำนวนธรรมชาติ อย่างไรก็ตาม ไม่ใช่ทุกลำดับเบื้องต้นจะถูกศึกษาในฐานะแนวคิดเรื่องความสามารถในการลดรูปได้ แนวคิดที่ศึกษาในทฤษฎีความสามารถในการคำนวณมีคุณสมบัติที่ไม่เป็นทางการว่า สามารถ ลดรูปได้เป็นก็ต่อเมื่อกระบวนการตัดสินใจใดๆ (อาจไม่มีประสิทธิภาพ) สำหรับสามารถแปลงเป็นกระบวนการตัดสินใจสำหรับ ได้อย่างมีประสิทธิภาพความสัมพันธ์ของความสามารถในการลดรูปที่แตกต่างกันนั้นแตกต่างกันในวิธีการที่อนุญาตให้กระบวนการแปลงดังกล่าวใช้ได้ ${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$

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

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

แนวคิดพื้นฐานที่สุดของการลดทอนได้คือการลดทอนแบบทัวริง (Turing reducibility) เซตของจำนวนธรรมชาติ สามารถลด ทอนแบบทัวริงไปเป็นเซตได้ก็ต่อเมื่อมีเครื่องจักรทัวริงแบบออราเคิล (oracle Turing machine ) ที่เมื่อทำงานโดยใช้เป็นเซตออราเคิล จะสามารถคำนวณฟังก์ชันตัวบ่งชี้ (ฟังก์ชันลักษณะเฉพาะ) ของ ได้หรือกล่าวอีกนัยหนึ่งสามารถลดทอนแบบทัวริงไปเป็น ได้ก็ต่อเมื่อมีอัลกอริทึมสำหรับคำนวณฟังก์ชันตัวบ่งชี้สำหรับโดยที่อัลกอริทึมนั้นมีวิธีการตอบคำถามในรูปแบบ " อยู่ใน หรือไม่ ?" ได้อย่างถูกต้อง${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle n}$${\displaystyle B}$

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

ความสามารถในการลดทอนที่แข็งแกร่ง ได้แก่

• ความสามารถในการลดรูปหนึ่งต่อหนึ่ง : สามารถลดรูปหนึ่งต่อหนึ่งได้เป็น ก็ต่อเมื่อมีฟังก์ชันหนึ่งต่อหนึ่ง ที่คำนวณได้ โดยที่สำหรับทุก${\displaystyle A}$${\displaystyle B}$${\displaystyle f}$${\displaystyle A(x)=B(f(x))}$${\displaystyle x}$
• ความสามารถในการลดรูปหลายหนึ่ง : สามารถลดรูปหลายหนึ่งไปเป็นได้หรือไม่ถ้ามีฟังก์ชันที่คำนวณได้ซึ่งสำหรับทุก${\displaystyle A}$${\displaystyle B}$${\displaystyle f}$${\displaystyle A(x)=B(f(x))}$${\displaystyle x}$
• ตารางความจริงสามารถลดรูปได้ : ตารางความจริงสามารถลดรูปได้เป็นถ้าสามารถลดรูปได้เป็นโดยใช้เครื่องทัวริง (ออราเคิล) เครื่องเดียวที่สร้างฟังก์ชันสมบูรณ์สัมพันธ์กับออราเคิลทุกตัว${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$
• สามารถลดรูปตารางความจริงแบบอ่อนได้ : สามารถลดรูปตารางความจริงแบบอ่อนได้เป็น ก็ต่อเมื่อมีการลดรูปทัวริงจากไปและมีฟังก์ชันที่คำนวณได้ซึ่งจำกัดการใช้งานเมื่อใดก็ตาม ที่ สามารถ ลดรูปตารางความจริงได้เป็นก็จะสามารถลดรูปตารางความจริงแบบอ่อนได้เป็น ด้วยเช่นกันเนื่องจากเราสามารถสร้างขอบเขตที่คำนวณได้ของการใช้งานได้โดยพิจารณาการใช้งานสูงสุดบนต้นไม้ของออราเคิลทั้งหมด ซึ่งจะมีอยู่หากการลดรูปเป็นแบบสมบูรณ์บนออราเคิลทั้งหมด${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle f}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$
• สามารถลดรูปได้ในเชิงบวก: สามารถลดรูปได้ในเชิงบวกไปยัง ก็ต่อเมื่อสามารถลดรูปตารางความจริงไปยังในลักษณะที่สามารถคำนวณสูตรที่ประกอบด้วยอะตอมในรูปแบบ สำหรับทุก ๆ โดยที่อะตอมเหล่านี้รวมกันด้วย "และ" และ "หรือ" โดยที่ "และ" ของ " และ" จะเป็น 1 ถ้า " และ" และอื่นๆ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x}$${\displaystyle B(0),B(1),...}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a=1}$${\displaystyle b=1}$
• ความสามารถในการลดทอนการแจงนับ : คล้ายกับความสามารถในการลดทอนเชิงบวก ซึ่งเกี่ยวข้องกับกระบวนการที่มีประสิทธิภาพของการแจงนับจากไปยัง${\displaystyle A}$${\displaystyle B}$
• โครงสร้างลดรูปเชิงแยก (Disjunctive reducible): คล้ายกับโครงสร้างลดรูปเชิงบวก (Positive reducible) แต่มีข้อจำกัดเพิ่มเติมคือ อนุญาตเฉพาะการใช้ "หรือ" เท่านั้น
• การลดรูปเชิงเชื่อม: คล้ายกับการลดรูปเชิงบวก แต่มีข้อจำกัดเพิ่มเติมคือ อนุญาตให้ใช้เฉพาะ "และ" เท่านั้น
• การลดรูปเชิงเส้น: คล้ายกับการลดรูปเชิงบวก แต่มีข้อจำกัดว่าอะตอมทั้งหมดในรูปแบบนั้นต้องรวมกันโดยใช้ การดำเนินการ แบบ OR เท่านั้นกล่าวอีกนัยหนึ่งคือ สามารถลดรูปเชิงเส้นได้เป็นก็ต่อเมื่อฟังก์ชันที่คำนวณได้คำนวณสำหรับแต่ละเซตจำกัดที่กำหนดเป็นรายการตัวเลขที่ชัดเจน โดยที่ก็ต่อเมื่อมีจำนวนสมาชิกเป็นเลขคี่ของ${\displaystyle B(n)}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x}$${\displaystyle F(x)}$${\displaystyle x\in A}$${\displaystyle F(x)}$${\displaystyle B}$

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

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

การลดรูปที่เข้มงวดที่ระบุไว้ข้างต้นจำกัดวิธีการเข้าถึงข้อมูลออราเคิลโดยกระบวนการตัดสินใจ แต่ไม่ได้จำกัดทรัพยากรการคำนวณที่มีอยู่แต่อย่างใด ดังนั้น หากเซตใดสามารถตัดสินได้ เซต นั้นก็จะสามารถลดรูปไปเป็นเซตใดๆ ก็ได้ภายใต้ความสัมพันธ์การลดรูปที่เข้มงวดใดๆ ที่ระบุไว้ข้างต้น^{[หมายเหตุ 1 ]}แม้ว่าเซตนั้นจะไม่สามารถตัดสินได้ในเวลาพหุนามหรือเวลาเลขชี้กำลังก็ตาม สิ่งนี้เป็นที่ยอมรับได้ในการศึกษาทฤษฎีความสามารถในการคำนวณ ซึ่งสนใจในความสามารถในการคำนวณเชิงทฤษฎี แต่ไม่สมเหตุสมผลสำหรับทฤษฎีความซับซ้อนของการคำนวณซึ่งศึกษาว่าเซตใดบ้างที่สามารถตัดสินได้ภายใต้ขอบเขตทรัพยากรเชิงอะซิมโทติกบางประการ ${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$

การลดรูปที่พบบ่อยที่สุดในทฤษฎีความซับซ้อนของการคำนวณคือการลดรูปในเวลาพหุนามเซตAสามารถลดรูปได้ในเวลาพหุนามไปยังเซต ได้ก็ต่อเมื่อมีฟังก์ชันในเวลาพหุนามfที่ทำให้สำหรับทุกn ∈ A n ∈ A อยู่ในเซต ก็ต่อเมื่อ n ∈ A อยู่ในเซตโดยพื้นฐานแล้ว การลดรูปนี้เป็นเวอร์ชันที่จำกัดทรัพยากรของการลดรูปแบบหลายต่อหนึ่ง การลดรูปอื่นๆ ที่จำกัดทรัพยากรจะถูกนำมาใช้ในบริบทอื่นๆ ของทฤษฎีความซับซ้อนของการคำนวณที่ต้องการขอบเขตทรัพยากรที่แตกต่างกัน ${\displaystyle B}$${\displaystyle n}$${\displaystyle n}$${\displaystyle A}$${\displaystyle f(n)}$${\displaystyle B}$

แม้ว่าความสามารถในการลดรูปของทัวริงจะเป็นความสามารถในการลดรูปทั่วไปที่สุดที่มีประสิทธิภาพ แต่ความสัมพันธ์ในการลดรูปที่อ่อนกว่าก็มักได้รับการศึกษา ความสามารถในการลดรูปเหล่านี้เกี่ยวข้องกับความสามารถในการกำหนดนิยามสัมพัทธ์ของเซตในทางเลขคณิตหรือทฤษฎีเซตซึ่งรวมถึง:

• ความสามารถในการลดรูปทางเลขคณิต : เซตหนึ่งเป็นเซตทางเลขคณิตในเซตหนึ่งถ้า เซต นั้นสามารถนิยามได้บนแบบจำลองมาตรฐานของเลขคณิตของพีอาโนโดยมี述语เพิ่มเติมสำหรับเซตนั้นหรือเทียบเท่ากัน ตามทฤษฎีบทของโพสต์ เซต A เป็นเซตทางเลขคณิตใน เซตหนึ่ง ก็ต่อเมื่อเซตนั้นสามารถลดรูปได้ด้วยการแปลงทัวริงไปยังเซตนั้น ซึ่งเป็นการกระโดดทัวริงลำดับที่ของ เซตนั้น สำหรับจำนวนธรรมชาติบางจำนวนลำดับชั้นทางเลขคณิตให้การจำแนกประเภทที่ละเอียดกว่าของความสามารถในการลดรูปทางเลขคณิต${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B^{(n)}}$${\displaystyle n}$${\displaystyle B}$${\displaystyle n}$
• ความสามารถในการลดรูปเชิงเลขคณิตขั้นสูง : เซตหนึ่งเป็นเซตเชิงเลขคณิตขั้นสูงในเซตหนึ่งถ้า เซต นั้นสามารถนิยามได้ (ดูที่ลำดับชั้นเชิงวิเคราะห์ ) บนแบบจำลองมาตรฐานของเลขคณิตของพีอาโนด้วย述语สำหรับเซตนั้น หรือ เทียบเท่ากัน เซตหนึ่งเป็นเซตเชิงเลขคณิตขั้นสูงในเซตหนึ่งก็ต่อเมื่อเซตนั้นสามารถลดรูปตามทัวริงได้เป็นเซตหนึ่ง ซึ่งเป็นการ กระโดดของทัวริงลำดับที่ของเซตหนึ่ง สำหรับลำดับที่เรียกซ้ำบางค่า${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle \Delta _{1}^{1}}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B^{(\alpha )}}$${\displaystyle \alpha }$${\displaystyle B}$${\displaystyle B}$${\displaystyle \alpha }$
• ความสามารถในการสร้างเชิงสัมพัทธ์ : เซตหนึ่งสามารถสร้างขึ้นได้จากเซตหนึ่งได้ก็ต่อเมื่อ เซต นั้นอยู่ใน ซึ่งเป็นแบบจำลองทรานซิทีฟที่เล็กที่สุดของทฤษฎีเซต ZFCที่ประกอบด้วยและลำดับ ทั้งหมด${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle L(B)}$${\displaystyle B}$

• สารานุกรมปรัชญาแห่งมหาวิทยาลัยสแตนฟอร์ด: ฟังก์ชันเรียกซ้ำ