Redutibilidade e Graus de Insolubilidade

A redutibilidade compara a dificuldade dos problemas transformando um no outro, e o agrupamento de problemas de igual dificuldade produz os graus de insolubilidade que estruturam o mundo além do computável.

Definition

Um problema reduz-se a outro quando um algoritmo com acesso a um solucionador para o segundo pode resolver o primeiro; problemas que se reduzem um ao outro partilham um grau de insolubilidade, e estes graus formam uma ordenação que mede a dificuldade algorítmica relativa.

Scope

Este tópico abrange a redutibilidade muitos-para-um e Turing, o uso de reduções para provar a indecidibilidade, a operação de salto de Turing que produz problemas estritamente mais difíceis, a hierarquia aritmética que classifica problemas por complexidade lógica, e resultados centrais da teoria dos graus, como a existência de graus intermediários.

Core questions

• Como podemos dizer que um problema insolúvel é mais difícil do que outro?
• Como as reduções são usadas tanto para provar a indecidibilidade quanto para organizar problemas?
• O que o salto de Turing produz, e por que é sempre estritamente mais difícil?
• Existem problemas estritamente entre o decidível e o problema da parada?

Key theories

Redutibilidade e o salto de Turing

A redutibilidade de Turing relaciona problemas por computação oráculo, e o salto de um problema, codificando a parada em relação a ele, é sempre estritamente mais difícil, gerando uma torre interminável de problemas cada vez mais difíceis.

Existência de graus intermediários

O teorema de Friedberg–Muchnik resolveu o problema de Post construindo problemas computavelmente enumeráveis que são indecidíveis, mas estritamente mais fáceis do que o problema da parada, usando o método da prioridade, mostrando que os graus possuem uma estrutura rica.

Clinical relevance

A técnica de redução é a ferramenta diária para provar que problemas são insolúveis ou, na teoria da complexidade, intratáveis: mostrar que um problema difícil conhecido se reduz a um novo transfere a dificuldade, que é exatamente como os resultados de indecidibilidade e NP-completude são estabelecidos em toda a matemática e ciência da computação.

History

Turing introduziu as máquinas oráculo em 1939, e Post, em 1944, enquadrou o estudo dos graus de insolubilidade e levantou o problema da existência de graus computavelmente enumeráveis intermediários. Friedberg e Muchnik resolveram-no independentemente em 1956–1957, inventando o método da prioridade, que se tornou uma técnica central da área.

Key figures

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

Seminal works

• soare2016
• rogers1987

Frequently asked questions

O que é uma redução, intuitivamente?

É uma forma de resolver um problema usando um solucionador para outro. Se você pode traduzir qualquer instância do problema A em uma instância do problema B de modo que as respostas correspondam, então B é pelo menos tão difícil quanto A, e uma solução para B produz uma solução para A.

Existem problemas mais difíceis do que o problema da parada?

Sim, infinitos. Aplicar o salto de Turing ao problema da parada produz um problema estritamente mais difícil, e repetir a operação constrói uma hierarquia infinita, de modo que a insolubilidade ocorre em graus ilimitados, em vez de um único nível.