Redução (teoria da recursão) - Reduction (recursion theory)

Na teoria da computabilidade , muitas relações de redutibilidade (também chamadas de reduções , redutibilidades e noções de redutibilidade ) são estudadas. Eles são motivados pela pergunta: dados conjuntos e de números naturais, é possível converter efetivamente um método para decidir a associação em um método para decidir a associação ? Se a resposta a esta pergunta for afirmativa, então se diz que é redutível a . ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle A}$ ${\ displaystyle B}$

O estudo das noções de redutibilidade é motivado pelo estudo dos problemas de decisão . Para muitas noções de redutibilidade, se qualquer conjunto não-computável é redutível a um conjunto, então também deve ser não-computável. Isso fornece uma técnica poderosa para provar que muitos conjuntos não são computáveis. ${\ displaystyle A}$${\ displaystyle A}$

Relações de redutibilidade

Uma relação de redutibilidade é uma relação binária em conjuntos de números naturais que é

• Reflexivo : cada conjunto é redutível a si mesmo.
• Transitivo : se um conjunto é redutível a um conjunto e é redutível a um conjunto, então é redutível a .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle C}$${\ displaystyle A}$${\ displaystyle C}$

Essas duas propriedades implicam que a redutibilidade é uma pré - ordem no conjunto de poderes dos números naturais. No entanto, nem todas as pré-encomendas são estudadas como noções de redutibilidade. As noções estudadas na teoria da computabilidade têm a propriedade informal que é redutível a se e somente se qualquer procedimento de decisão (possivelmente não efetivo) para pode ser efetivamente convertido em um procedimento de decisão para . As diferentes relações de redutibilidade variam nos métodos que permitem que tal processo de conversão use. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$

Graus de uma relação de redutibilidade

Toda relação de redutibilidade (na verdade, toda pré-ordem) induz uma relação de equivalência no conjunto de poderes dos números naturais em que dois conjuntos são equivalentes se e somente se cada um for redutível ao outro. Na teoria da computabilidade, essas classes de equivalência são chamadas de graus da relação de redutibilidade. Por exemplo, os graus de Turing são as classes de equivalência de conjuntos de naturais induzidas pela redutibilidade de Turing.

Os graus de qualquer relação de redutibilidade são parcialmente ordenados pela relação da seguinte maneira. Seja uma relação de redutibilidade e seja e seja dois de seus graus. Então, se e somente se houver um conjunto em e um conjunto de tal forma . Isto é equivalente à propriedade que, para cada conjunto em e cada conjunto em , porque nenhum dois jogos em C são equivalentes e quaisquer dois conjuntos em são equivalentes. É comum, como mostrado aqui, usar a notação em negrito para denotar graus. ${\ 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}$

Redutibilidade de Turing

A noção de redutibilidade mais fundamental é a redutibilidade de Turing . Um conjunto de números naturais é Turing redutível a um conjunto se e somente se houver uma máquina de Turing oráculo que, quando executada como seu conjunto oráculo, calculará a função indicadora (função característica) de . De forma equivalente, Turing é redutível a se, e somente se, houver um algoritmo para calcular a função do indicador, desde que o algoritmo seja fornecido com um meio de responder corretamente às perguntas da forma "Está em ?". ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle n}$${\ displaystyle B}$

A redutibilidade de Turing serve como linha divisória para outras noções de redutibilidade porque, de acordo com a tese de Church-Turing , é a relação de redutibilidade mais geral que é eficaz. As relações de redutibilidade que implicam na redutibilidade de Turing passaram a ser conhecidas como redutibilidades fortes , enquanto aquelas que estão implícitas na redutibilidade de Turing são redutibilidades fracas. Equivalentemente, uma relação de redutibilidade forte é aquela cujos graus formam uma relação de equivalência mais fina do que os graus de Turing, enquanto uma relação de redutibilidade fraca é aquela cujos graus formam uma relação de equivalência mais grosseira do que a equivalência de Turing.

Reduções mais fortes do que redutibilidade de Turing

As fortes redutibilidades incluem

• Redutibilidade um-um : é um-um redutível para se houver uma função um-para-um computável com para todos .${\ displaystyle A}$${\ displaystyle B}$ ${\ displaystyle f}$${\ displaystyle A (x) = B (f (x))}$${\ displaystyle x}$
• Redutibilidade muitos-um : é redutível muitos-um para se houver uma função computável com para todos .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle f}$${\ displaystyle A (x) = B (f (x))}$${\ displaystyle x}$
• Tabela de verdade redutível : é a tabela de verdade redutível a se Turing é redutível a por meio de uma única máquina de Turing (oráculo) que produz uma função total em relação a cada oráculo.${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$
• Tabela de verdade fraca redutível : é a tabela de verdade fraca redutível a se houver uma redução de Turing de a e uma função computável que limita o uso . Sempre que a tabela de verdade é redutível a , também é a tabela de verdade fraca redutível a , uma vez que se pode construir um limite computável sobre o uso considerando o uso máximo sobre a árvore de todos os oráculos, que existirá se a redução for total em todos os oráculos .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle f}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$
• Redutível positivo: é redutível positivamente a se e somente se a tabela de verdade é redutível a de uma forma que se possa calcular para cada uma fórmula que consiste em átomos da forma tal que esses átomos são combinados por e's e ou's, onde o e de e é 1 se e e assim por diante.${\ 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}$
• Redutibilidade de enumeração : semelhante à redutibilidade positiva, relacionada ao procedimento efetivo de enumerabilidade de a .${\ displaystyle A}$${\ displaystyle B}$
• Redutível disjuntivo: Semelhante ao redutível positivo com a restrição adicional de que apenas ou são permitidos.
• Redutibilidade conjuntiva: semelhante à redutibilidade positiva com a restrição adicional de que apenas e são permitidos.
• Redutibilidade linear: semelhante à redutibilidade positiva, mas com a restrição de que todos os átomos da forma são combinados por ors exclusivos . Em outras palavras, é linear redutível a se, e somente se, uma função computável calcula para cada um um conjunto finito dado como uma lista explícita de números tal que se e somente se contém um número ímpar de elementos de .${\ displaystyle B (n)}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle x}$${\ displaystyle F (x)}$${\ displaystyle x \ in A}$${\ displaystyle F (x)}$${\ displaystyle B}$

Muitos deles foram introduzidos por Post (1944). Post estava procurando por um conjunto não computável e computávelmente enumerável ao qual o problema da parada não poderia ser reduzido por Turing. Como ele não pôde construir tal conjunto em 1944, ele trabalhou em problemas análogos para as várias redutibilidades que introduziu. Desde então, essas redutibilidades têm sido objeto de muitas pesquisas, e muitas relações entre elas são conhecidas.

Redutibilidades limitadas

Uma forma limitada de cada uma das fortes redutibilidades acima pode ser definida. O mais famoso deles é a redução da tabela de verdade limitada, mas também há Turing limitada, tabela de verdade fraca limitada e outros. Os três primeiros são os mais comuns e baseiam-se no número de consultas. Por exemplo, um conjunto é uma tabela de verdade limitada, redutível a se e somente se a máquina de Turing computando em relação a computar uma lista de até números, consulta esses números e então termina para todas as respostas possíveis do oráculo; o valor é uma constante independente de . A diferença entre a tabela de verdade fraca limitada e a redução de Turing limitada é que no primeiro caso, as consultas até devem ser feitas ao mesmo tempo, enquanto no segundo caso, as consultas podem ser feitas uma após a outra. Por essa razão, há casos em que Turing é limitado redutível a, mas não uma tabela de verdade fraca redutível a . ${\ 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}$

Fortes reduções na complexidade computacional

As fortes reduções listadas acima restringem a maneira pela qual as informações do oráculo podem ser acessadas por um procedimento de decisão, mas não limitam de outra forma os recursos computacionais disponíveis. Assim, se um conjunto é decidível, então é redutível a qualquer conjunto sob qualquer uma das relações de redutibilidade fortes listadas acima, mesmo se não for decidível em tempo polinomial ou em tempo exponencial. Isso é aceitável no estudo da teoria da computabilidade, que está interessada na computabilidade teórica, mas não é razoável para a teoria da complexidade computacional , cujos estudos cujos conjuntos podem ser decididos sob certos limites de recursos assintóticos. ${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$

A redutibilidade mais comum na teoria da complexidade computacional é a redutibilidade em tempo polinomial ; um conjunto A é redutível em tempo polinomial a um conjunto se houver uma função em tempo polinomial f tal que, para cada , está em se e somente se estiver em . Essa redutibilidade é, essencialmente, uma versão limitada por recursos da redutibilidade muitos-um. Outras redutibilidades limitadas por recursos são usadas em outros contextos da teoria da complexidade computacional, onde outros limites de recursos são de interesse. ${\ displaystyle B}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle A}$${\ displaystyle f (n)}$${\ displaystyle B}$

Reduções mais fracas do que a redutibilidade de Turing

Embora a redutibilidade de Turing seja a redutibilidade mais geral que é eficaz, relações de redutibilidade mais fracas são comumente estudadas. Essas redutibilidades estão relacionadas à definibilidade relativa dos conjuntos em relação à aritmética ou à teoria dos conjuntos. Eles incluem:

• Redutibilidade aritmética : Um conjunto é aritmético em um conjunto se for definível sobre o modelo padrão da aritmética de Peano com um predicado extra para . Equivalentemente, de acordo com o teorema de Post , A é aritmético em se, e somente se, Turing é redutível a , o ésimo salto de Turing de , para algum número natural . A hierarquia aritmética fornece uma classificação mais precisa da redutibilidade aritmética.${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B ^ {(n)}}$${\ displaystyle n}$${\ displaystyle B}$${\ displaystyle n}$
• Redutibilidade hiperaritmética : um conjunto é hiperaritmético em um conjunto se for definível (consulte a hierarquia analítica ) sobre o modelo padrão da aritmética de Peano com um predicado para . Equivalentemente, é hiperaritmético em se, e somente se, Turing é redutível a , o ésimo salto de Turing de , para alguns - ordinal recursivo .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle \ Delta _ {1} ^ {1}}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B ^ {(\ alpha)}}$${\ displaystyle a}$${\ displaystyle B}$${\ displaystyle B}$ ${\ displaystyle a}$
• Construtibilidade relativa : um conjunto é relativamente construtível a partir de um conjunto se estiver em , o menor modelo transitivo da teoria de conjuntos ZFC contendo todos os ordinais.${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle L (B)}$${\ displaystyle B}$

Referências

• K. Ambos-Spies e P. Fejer, 2006. " Degrees of Unsolvability ". Pré-impressão não publicada.
• P. Odifreddi, 1989. Teoria da Recursão Clássica , North-Holland. ISBN  0-444-87295-7
• P. Odifreddi, 1999. Teoria da Recursão Clássica, Volume II , Elsevier. ISBN  0-444-50205-X
• E. Post, 1944, "Conjuntos recursivamente enumeráveis ​​de inteiros positivos e seus problemas de decisão", Bulletin of the American Mathematical Society , volume 50, páginas 284-316.
• H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability , segunda edição 1987, MIT Press. ISBN  0-262-68052-1 (brochura), ISBN  0-07-053522-1
• G Sacks, 1990. Teoria da Recursão Superior , Springer-Verlag. ISBN  3-540-19305-7