Tính quy giản và các bậc không giải được

Tính quy giản so sánh độ khó của các bài toán bằng cách biến đổi bài toán này thành bài toán khác, và việc nhóm các bài toán có độ khó tương đương sẽ tạo ra các bậc không giải được, cấu trúc hóa thế giới vượt ra ngoài khả năng tính toán.

Definition

Một bài toán được quy giản về bài toán khác khi một thuật toán có quyền truy cập vào bộ giải cho bài toán thứ hai có thể giải quyết bài toán thứ nhất; các bài toán quy giản về nhau có chung một bậc không giải được, và các bậc này tạo thành một thứ tự đo lường độ khó thuật toán tương đối.

Scope

Chủ đề này bao gồm tính quy giản nhiều-một và Turing, việc sử dụng các phép quy giản để chứng minh tính không quyết định được, phép toán nhảy Turing tạo ra các bài toán khó hơn một cách nghiêm ngặt, hệ thống phân cấp số học phân loại các bài toán theo độ phức tạp logic, và các kết quả trung tâm của lý thuyết bậc như sự tồn tại của các bậc trung gian.

Core questions

• Làm thế nào chúng ta có thể nói một bài toán không giải được khó hơn bài toán khác?
• Các phép quy giản được sử dụng như thế nào để vừa chứng minh tính không quyết định được vừa để tổ chức các bài toán?
• Phép nhảy Turing tạo ra điều gì, và tại sao nó luôn khó hơn một cách nghiêm ngặt?
• Có bài toán nào nằm chính xác giữa bài toán quyết định được và bài toán dừng không?

Key theories

Tính quy giản và phép nhảy Turing

Tính quy giản Turing liên hệ các bài toán bằng cách tính toán oracle, và phép nhảy của một bài toán, mã hóa việc dừng tương đối với nó, luôn khó hơn một cách nghiêm ngặt, tạo ra một tháp vô tận các bài toán ngày càng khó hơn.

Sự tồn tại của các bậc trung gian

Định lý Friedberg–Muchnik đã giải quyết vấn đề của Post bằng cách xây dựng các bài toán đếm được bằng máy tính mà không quyết định được nhưng lại dễ hơn một cách nghiêm ngặt so với bài toán dừng, sử dụng phương pháp ưu tiên, cho thấy các bậc có cấu trúc phong phú.

Clinical relevance

Kỹ thuật quy giản là công cụ hàng ngày để chứng minh các bài toán không giải được hoặc, trong lý thuyết độ phức tạp, không thể xử lý được: việc chỉ ra rằng một bài toán khó đã biết quy giản về một bài toán mới sẽ chuyển giao độ khó, đây chính xác là cách các kết quả về tính không quyết định được và NP-hoàn chỉnh được thiết lập trong toán học và khoa học máy tính.

History

Turing đã giới thiệu các máy oracle vào năm 1939, và Post vào năm 1944 đã định hình nghiên cứu về các bậc không giải được và đặt ra vấn đề liệu có tồn tại các bậc đếm được bằng máy tính trung gian hay không. Friedberg và Muchnik đã độc lập giải quyết vấn đề này vào năm 1956–1957 bằng cách phát minh ra phương pháp ưu tiên, trở thành một kỹ thuật trung tâm của lĩnh vực này.

Key figures

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

Seminal works

• soare2016
• rogers1987

Frequently asked questions

Một phép quy giản, một cách trực quan, là gì?

Đó là một cách giải quyết một bài toán bằng cách sử dụng bộ giải cho một bài toán khác. Nếu bạn có thể dịch bất kỳ trường hợp nào của bài toán A thành một trường hợp của bài toán B sao cho các câu trả lời khớp nhau, thì B ít nhất cũng khó bằng A, và một giải pháp cho B sẽ mang lại một giải pháp cho A.

Có bài toán nào khó hơn bài toán dừng không?

Có, vô số. Áp dụng phép nhảy Turing cho bài toán dừng sẽ tạo ra một bài toán khó hơn một cách nghiêm ngặt, và lặp lại phép toán này sẽ xây dựng một hệ thống phân cấp vô tận, do đó tính không giải được tồn tại ở các bậc không giới hạn chứ không phải ở một cấp độ duy nhất.