FP (Complexidade)
Na teoria da complexidade computacional, a complexidade de classe FP é o conjunto de problemas de função que podem ser resolvidos por uma máquina de Turing determinística em tempo polinomial; é a versão funcional da classe P de problemas de decisão . Grosseiramente falando, é a classe de funções que podem ser eficientemente calculadas em computadores clássicos sem randomização.
FP é formalmente definida da seguinte forma:
- Uma relação binária P(x,y) pertence a FP se, e somente se, existe um algoritmo determinístico de tempo polinomial que, dado x, pode encontrar algum y tal que P(x,y), se verifica.
A diferença entre a FP e P é que os problemas em P tem respostas do tipo sim/não, um bit, enquanto que problemas em FP podem ter qualquer saída que pode ser computada em tempo polinomial. Por exemplo, a adição de dois números é um problema FP, enquanto determinar se a sua soma é ímpar está em P.
Como P e FP são intimamente relacionadas, NP está intimamente relacionada com FNP.
Problemas de função de tempo polinomial são fundamentais na definição de reduções em tempo polinomial, que são usadas por sua vez para definir a classe dos problemas NP-completos.
Em razão do fato de que uma máquina que usa espaço logarítmico tem no máximo uma quantidade polinomial de configurações, FL, o conjunto de problemas de função, que pode ser calculado em logspace, está contido em FP. Não se sabe se FL = FP; isso é análogo ao problema de se determinar se as classes de decisão P e L são iguais.
Referências[editar | editar código-fonte]
- Bürgisser, Peter (2000). Completeness and reduction in algebraic complexity theory. Col: Algorithms and Computation in Mathematics. 7. Berlin: Springer-Verlag. p. 66. ISBN 3-540-66752-0. Zbl 0948.68082
- Rich, Elaine (2008). «28.10 "The problem classes FP and FNP"». Automata, computability and complexity: theory and applications. [S.l.]: Prentice Hall. pp. 689–694. ISBN 0-13-228806-0