Problema de função

Em teoria da complexidade computacional, um problema de função é um problema computacional onde uma única saída (de uma ) é 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 , 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 é da linha de funções de problemas que podem ser resolvidos pela Máquina de Turing em , e é da linha de funções que podem ser resolvidas por uma Máquina de Turing não determinística em . 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 (ou 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 ser o número de arestas e ser o peso da aresta . Primeiro, redimensione e mexa os pesos das arestas, atribuindo a aresta the new weight . 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 . Encontre o peso do menor caminho Hamiltoniano por busca binária: existe um caminho Hamiltonian com peso ; existe um caminho com peso etc. Então, tendo encontrado os pesos do menor caminho Hamilton, determine quais arestas estão no caminho perguntando para cada aresta se existe um caminho Hamiltoniano com peso para o grafo modificado de modo que a aresta tenha peso (se não existe tal caminho no gráfico modificado, então a aresta deve estar no menor caminho para o grafo original). Isso coloca o problema do caixeiro viajante na classe de complexidade FPNP (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.