Reducibiliteit en graden van onoplosbaarheid

Reducibiliteit vergelijkt de moeilijkheidsgraad van problemen door het ene in het andere te transformeren, en het groeperen van problemen van gelijke moeilijkheidsgraad levert de graden van onoplosbaarheid op die de wereld voorbij het berekenbare structureren.

Definition

Een probleem reduceert tot een ander wanneer een algoritme met toegang tot een oplosser voor het tweede het eerste kan oplossen; problemen die tot elkaar reduceren, delen een graad van onoplosbaarheid, en deze graden vormen een ordening die de relatieve algoritmische moeilijkheidsgraad meet.

Scope

Dit onderwerp omvat vele-één- en Turing-reducibiliteit, het gebruik van reducties om onbeslisbaarheid te bewijzen, de Turing-sprongoperatie die strikt moeilijkere problemen produceert, de rekenkundige hiërarchie die problemen classificeert op logische complexiteit, en centrale resultaten van de graadtheorie zoals het bestaan van intermediaire graden.

Core questions

• Hoe kunnen we zeggen dat het ene onoplosbare probleem moeilijker is dan het andere?
• Hoe worden reducties gebruikt om zowel onbeslisbaarheid te bewijzen als problemen te organiseren?
• Wat produceert de Turing-sprong, en waarom is deze altijd strikt moeilijker?
• Zijn er problemen strikt tussen het beslisbare en het haltingprobleem?

Key theories

Reducibiliteit en de Turing-sprong

Turing-reducibiliteit relateert problemen door middel van orakelberekening, en de sprong van een probleem, die het stoppen relatief daartoe codeert, is altijd strikt moeilijker, wat een oneindige toren van steeds moeilijkere problemen genereert.

Bestaan van intermediaire graden

Het Friedberg–Muchnik-theorema loste Post's probleem op door berekenbaar opsombare problemen te construeren die onbeslisbaar zijn, doch strikt gemakkelijker dan het haltingprobleem, gebruikmakend van de prioriteitsmethode, wat aantoont dat de graden een rijke structuur hebben.

Clinical relevance

De reductietechniek is het alledaagse werkpaard voor het bewijzen dat problemen onoplosbaar zijn of, in de complexiteitstheorie, onhandelbaar: aantonen dat een bekend moeilijk probleem reduceert tot een nieuw probleem, draagt de moeilijkheidsgraad over, wat precies is hoe onbeslisbaarheids- en NP-volledigheidsresultaten worden vastgesteld in de wiskunde en informatica.

History

Turing introduceerde orakelmachines in 1939, en Post formuleerde in 1944 de studie van graden van onoplosbaarheid en stelde het probleem van het bestaan van intermediaire berekenbaar opsombare graden. Friedberg en Muchnik losten dit onafhankelijk op in 1956–1957 door de prioriteitsmethode uit te vinden, die een centrale techniek van het vakgebied werd.

Key figures

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

Seminal works

• soare2016
• rogers1987

Frequently asked questions

Wat is een reductie, intuïtief?

Het is een manier om het ene probleem op te lossen met behulp van een oplosser voor een ander. Als je elke instantie van probleem A kunt vertalen naar een instantie van probleem B zodat de antwoorden overeenkomen, dan is B op zijn minst even moeilijk als A, en een oplossing voor B levert een oplossing voor A op.

Zijn er problemen die moeilijker zijn dan het haltingprobleem?

Ja, oneindig veel. Het toepassen van de Turing-sprong op het haltingprobleem levert een strikt moeilijker probleem op, en het herhalen van de operatie bouwt een eindeloze hiërarchie op, zodat onoplosbaarheid in onbegrensde graden voorkomt in plaats van in één enkel niveau.