# Redutibilidade

Redutibilidade é o principal método de provar que problemas são computacionalmente insolúveis. Sabemos que a Máquina de Turing é um modelo de um computador de propósito geral e que existem diversos exemplos de problemas que são solúveis por máquinas de Turing como também problemas computacionalmente insolúveis. Ao se examinar problemas insolúveis introduzimos o método de redutibilidade que prova que alguns problemas são computacionalmente insolúveis.
A Redutibilidade não diz nada em resolver A ou B sozinhos, mas somente sobre a solubilidade de A na presença de um método para resolver B. Como exemplo de Redutibilidade em aspectos matemáticos podemos citar que a medição da área de um retângulo se reduz ao problema de se medir seu comprimento e largura. O Problema de se resolver um sistema de equações lineares se reduz ao problema de se inverter uma matriz. Quando A é redutível a B, resolver A não pode ser mais difícil que resolver B, porque uma solução para B dá solução para A. Em resumo, nosso método para provar que um problema é indecidível será mostrar que algum outro problema já conhecido como sendo indecidível se reduz a ele. Aborda uma determinada entrada para Máquina de Turing, estabelecendo uma relação de redução para definirmos se a máquina pára (aceitando ou rejeitando) sobre a entrada anteriormente definida.
Ex: Problema = {<M,w> | M é uma MT e M pára sobre a entrada w}.
A principal chave da questão é o problema de entrada e o de comportamento. Vemos que um faz a redução do outro (a entrada para uma máquina, definindo o estado de comportamento). A Redutibilidade é diretamente ligada com a indecidibilidade.Os teoremas ilustram as estratégias para provar que um problema é indecidível. O método da Redutibilidade faz uso de notações, exceto,quando nos referimos a própria Máquina de Turing,sendo essa provada através do método da diagonalização. Diagonalização é uma técnica de comparação de métodos ou problemas, envolvendo tamanhos,espaços ou quantidades. Indecidibilidade é um problema de decisão com conjunto de números naturais; o "problema" é determinar se um número em particular pertence ao conjunto ou notação, afetando em sua decisão. O método de história da computação é uma técnica importante para provar que uma entrada é redutível a certas linguagens.Esse método é freqüentemente útil quando o problema a ser mostrado como indecidível envolve testar a existência de algo. A história de computação para uma máquina de Turing sobre uma entrada é simplesmente a seqüência de configurações pelas quais a máquina passa à medida que processa a entrada. É um registro completo da computação dessa máquina.
Tomemos duas definições que descrevem essas vias:
Primeira Definição: Seja M uma máquina de Turing e w uma cadeia de entrada.Uma história de computação de aceitação para M sobre w é uma seqüência de configurações, C1, C2. . . Cn, onde C1 é a configuração inicial de M sobre w,Cn é uma configuração de aceitação de M, e cada Ci segue legitimamente de Ci-1 conforme as regras de M. Uma história de computação de rejeição para M sobre w é definida similarmente, exceto que Cn é uma configuração de rejeição.
Segunda Definição: Um autômato linearmente limitado é um tipo restrito de máquina de Turing na qual a cabeça de leitura-escrita não é permitida mover-se para fora da parte da fita contendo a entrada. Se a máquina tentar mover sua cabeça para além de qualquer uma das extremidades da entrada, a cabeça permanecerá onde está, da mesma maneira que a cabeça não se movimentará para além da extremidade esquerda da fita de uma máquina de Turing ordinária.
Traduzindo a segunda via, podemos dizer que um autômato limitado é uma Máquina de Turing com quantidade limitada de memória.Ela só pode resolver problemas que requerem memória que possa caber dentro da fita usada para entrada. A Indecidibilidade não está somente confinada a problemas relacionados a autômatos. É a formalização da Redutibilidade. A noção de reduzir um problema a outro pode ser definida formalmente de várias maneiras, a forma mais simples é definida por Mapeamento. De forma resumida, dizemos que ser capaz de reduzir um problema A ao problema B usando uma redução por mapeamento significa que existe uma função computável que converte instâncias do problema A para instâncias do problema B. Uma Máquina de Turing computa uma função iniciando com a entrada para a função sobre a fita e parando com a saída da função sobre a fita.

## Redução

Uma Redução (complexidade) é uma maneira de converter um problema em outro de forma que uma solução para o segundo problema possa ser usada para resolver o primeiro. Essas redutibilidades aparecem frequentemente no dia-a-dia, mesmo que em geral não nos refiramos a ela dessa forma.
Por exemplo, supondo que uma pessoa deseje se orientar em uma cidade nova. Seria muito mais fácil se a pessoa em questão tivesse consigo um mapa. Consequentemente o problema pode ser reduzido ao problema de se obter um mapa da nova cidade em que se está.
A redutibilidade sempre envolve dois problemas, que denominamos A e B. Se A se reduz a B, podemos usar uma solução para B para resolver A. Assim no nosso exemplo, A é o problema de se orientar na cidade e B é o problema de se se obter um mapa da cidade. Notemos que a redutibilidade não diz nada sobre resolver A ou B separados, mas apenas sobre a solubilidade de A na presença de uma solução para B.
O que se segue são exemplos adicionais de redutibilidades. O problema de se viajar de Recife a Londres se reduz ao problema de se comprar uma passagem aérea entre as duas cidades. Esse problema, por sua vez, se reduz ao problema de ganhar o dinheiro para passagem. E esse último problema se reduz ao problema de se encontrar uma fonte de renda.

## Problemas Matemáticos

A redutibilidade também se encontra em problemas matemáticos. Por exemplo, o problema de se medir a área de um retângulo se reduz ao problema de se medir seu comprimento e largura, assim como em um quadrado o problema se reduziria a encontrarmos a medida de um de seus lados. O problema de se resolver um sistema de equações lineares se reduz ao problema de se inverter uma Matriz.

## Teoria da Complexidade

A redutibilidade desempenha um importante papel na classificação de problemas por decidibilidade e, posteriormente, em teoria da complexidade também.
Quando A é redutível a B, resolver A não pode ser mais difícil do que resolver B, porque uma solução para B dá uma solução para A. Em termos de teoria da computabilidade, se A for redutível a B e B for decidível, A também será decidível. Equivalentemente, se A for indecidível e redutível a B, B será indecidível. Essa última versão é a chave para provar que vários problemas são indecidíveis.
Em resumo, um excelente método para provar que um problema é indecidível será mostrar que algum outro problema já conhecido como sendo indecidível se reduz a ele

## Redutibilidade por mapeamento em tempo polinomial

Uma linguagem A é redutível por mapeamento em tempo polinomial, ou simplesmente redutível em tempo polinomial, à linguagem B se existe uma função computável em tempo polinomial onde para toda w, w pertença a A se e somente se f(w) pertença a B. A função é denominada redução de tempo polinomial de A para B. Em alguns livros-texto redutibilidade por mapeamento também pode ser chamado de redutibilidade muitos-para-um.
A linguagem A é redutível por mapeamento à linguagem B, escrito A ≤$_m$ B, se existe uma função computável ƒ: Σ → Σ, onde para toda w, w ∈ A ←→ ƒ(w) ∈ B. A função ƒ é denominada a redução de A para B.

## Funções computáveis

Uma máquina de Turing computa uma função iniciando com a entrada para a função sobre a fita e parando com a saída da função sobre a fita. Uma função ƒ: Σ → Σ* é uma função computável se alguma máquina de Turing M, sobre toda entrada w, pára com exatamente ƒ(w) sobre a fita. Todas as operações aritméticas usuais sobre inteiros são funções computáveis. Por exemplo, podemos construir uma máquina que toma entrada <m,n> e retorna m+n, a soma de m e n.

## Relações de redutibilidade

Uma relação de redutibilidade é uma relação binária em conjuntos de números naturais que são:
* Reflexiva : todo conjunto é redutível a ele mesmo.
* Transitiva : Se um conjunto A é redutível a um conjunto B e um conjunto B é redutível a um conjunto C, então A é redutível a C.
As noções de redutibilidade estudadas na teória da computação têm a propriedade informal de que A é redutível a B se e somente se algum (possivelmente até mesmo não efetivo) procedimento de decisão para B pode ser efetivamente convertido para um procedimento de decisão para A. As diferentes relações de redutibilidade variam de métodos para métodos, que permitem ou não o uso de processos de conversão.