Problema de função

Em teoria da complexidade computacional, um problema de função é um problema computacional onde uma única saída (de uma função total) é esperada pra cada entrada, mas a sáida é mais complexa do que um problema de decisão, isto é, não é apenas SIM ou NÃO. Notáveis exemplos incluem o problema do caixeiro viajante, que indaga qual rota foi feita pelo caixeiro viajante, e o problema da fatoração de inteiros, que indaga pela lista de fatores.

Problemas de função são mais trabalhosos de estudar que os problemas de decisão porque eles não tem nenhuma analogia óbvia em termos de linguagem, e porque a noção de redução entre problemas é mais sutil do que você ter transformar a saída, bem como a entrada. Problemas de função podem ser colocados dentro de problemas de classe de complexidade, assim como nos problemas de decisão. Por exemplo FP é da linha de funções de problemas que podem ser resolvidos pela Máquina de Turing em tempo polinomial, e FNP é da linha de funções que podem ser resolvidas por uma Máquina de Turing não determinística em tempo polinomial.

Por todas os problemas de função em que a solução é polinomialmente limitada, há em um análogo problema de decisão que o problema de função pode ser resolvido por uma redução em tempo polinomial para aquele problema de decisão. Por exemplo, o problema de decisão análogo ao do caixeiro viajante é:

Dado um grafo direcionado ponderado e um inteiro K, existe um Caminho Hamiltoniano (ou Ciclo Hamiltoniano se o caixeiro viajante necessita voltar pra casa) o peso total inferior ou igual a K?

Dada uma solução para esse problema, nós podemos resolver o problema do caixeiro viajante como é mostrado a seguir. Deixe $n$ ser o número de arestas e $w_{i}$ ser o peso da aresta $i$. Primeiro, redimensione e mexa os pesos das arestas, atribuindo a aresta $i$ the new weight $w'_{i}=2^{(n+1)}w_{i}+2^{i}$. Isso não muda o menor caminho Hamiltoniano, mas tenha certeza de que ele é único. Agora, adicione os pesos de todas as arestas para ter um peso total $M$. Encontre o peso do menor caminho Hamiltoniano por busca binária: existe um caminho Hamiltonian com peso $<M/2$; existe um caminho com peso $<M/4$ etc. Então, tendo encontrado os pesos $W$ do menor caminho Hamilton, determine quais arestas estão no caminho perguntando para cada aresta $i$ se existe um caminho Hamiltoniano com peso $W$ para o grafo modificado de modo que a aresta $i$ tenha peso $W+1$ (se não existe tal caminho no gráfico modificado, então a aresta $i$ deve estar no menor caminho para o grafo original).

Isso coloca o problema do caixeiro viajante na classe de complexidade FP^NP (a classe de problemas de funções que podem ser solucionadas em tempo polinomial em uma Máquina de Turing Determinística com uma Máquina Oráculo para um problema em NP), e de fato ele é completo para aquela classe.

Referências

• Raymond Greenlaw, H. James Hoover, Fundamentals of the theory of computation: principles and practice, Morgan Kaufmann, 1998, ISBN 1-55860-474-X, p. 45-51
• Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2008, ISBN 0-13-228806-0, section 28.10 "The problem classes FP and FNP", pp. 689-694

Ver também

• Problema de decisão
• Problema de busca
• Problema de otimização