Redukálhatóság és a megoldhatatlansági fokok

A redukálhatóság a problémák nehézségét hasonlítja össze azáltal, hogy az egyiket a másikba transzformálja, és az azonos nehézségű problémák csoportosítása hozza létre a megoldhatatlansági fokokat, amelyek a számítható világon túli struktúrát adják.

Definition

Egy probléma akkor redukálható egy másikra, ha egy algoritmus, amely hozzáfér a második probléma megoldójához, meg tudja oldani az elsőt; az egymásra redukálható problémák osztoznak egy megoldhatatlansági fokon, és ezek a fokok egy rendezést alkotnak, amely a relatív algoritmikus nehézséget méri.

Scope

Ez a téma magában foglalja a sok-egy (many-one) és a Turing-redukálhatóságot, a redukciók alkalmazását a eldönthetetlenség bizonyítására, a Turing-ugrás (Turing jump) műveletet, amely szigorúan nehezebb problémákat eredményez, az aritmetikai hierarchiát, amely a problémákat logikai komplexitásuk szerint osztályozza, valamint a fokelmélet (degree theory) központi eredményeit, mint például a köztes fokok létezését.

Core questions

• Hogyan mondhatjuk, hogy az egyik megoldhatatlan probléma nehezebb, mint a másik?
• Hogyan használják a redukciókat az eldönthetetlenség bizonyítására és a problémák rendszerezésére?
• Mit eredményez a Turing-ugrás, és miért mindig szigorúan nehezebb?
• Vannak-e problémák szigorúan a eldönthető és a megállási probléma között?

Key theories

Redukálhatóság és a Turing-ugrás

A Turing-redukálhatóság orákulum-számítással (oracle computation) kapcsolja össze a problémákat, és egy probléma ugrása, amely a hozzá viszonyított megállást kódolja, mindig szigorúan nehezebb, végtelen tornyot generálva a egyre nehezebb problémákból.

Köztes fokok létezése

A Friedberg–Muchnik-tétel Post problémáját oldotta meg azáltal, hogy számíthatóan felsorolható (computably enumerable) problémákat konstruált, amelyek eldönthetetlenek, mégis szigorúan könnyebbek, mint a megállási probléma, a prioritási módszer (priority method) alkalmazásával, megmutatva, hogy a fokok gazdag struktúrával rendelkeznek.

Clinical relevance

A redukciós technika a mindennapi munkaeszköz a problémák megoldhatatlanságának, vagy a komplexitáselméletben az intrakabilitásának bizonyítására: megmutatva, hogy egy ismert nehéz probléma egy újabbra redukálható, átviszi a nehézséget, és pontosan így állapítják meg az eldönthetetlenségi és NP-teljességi eredményeket a matematikában és a számítástechnikában.

History

Turing 1939-ben vezette be az orákulumgépeket, Post pedig 1944-ben keretezte a megoldhatatlansági fokok tanulmányozását, és felvetette azt a problémát, hogy léteznek-e köztes számíthatóan felsorolható fokok. Friedberg és Muchnik egymástól függetlenül oldották meg 1956–1957-ben a prioritási módszer feltalálásával, amely a téma központi technikájává vált.

Key figures

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

Seminal works

• soare2016
• rogers1987

Frequently asked questions

Mi a redukció, intuitívan?

Ez egy módja annak, hogy az egyik problémát egy másik problémához tartozó megoldó segítségével oldjuk meg. Ha egy A probléma bármely példányát át tudjuk fordítani egy B probléma példányává úgy, hogy a válaszok egyezzenek, akkor B legalább olyan nehéz, mint A, és B megoldása A megoldását eredményezi.

Vannak-e a megállási problémánál nehezebb problémák?

Igen, végtelen sok. A Turing-ugrás alkalmazása a megállási problémára szigorúan nehezebb problémát eredményez, és a művelet ismétlése végtelen hierarchiát épít fel, így a megoldhatatlanság nem egyetlen szinten, hanem korlátlan fokokban jelentkezik.