Editing FP (complexity) (section)

{{Short description|Complexity class}}
In [[computational complexity theory]], the [[complexity class]] '''FP''' is the set of [[function problem]]s that can be solved by a [[deterministic Turing machine]] in [[polynomial time]]. It is the function problem version of the [[decision problem]] class '''[[P (complexity)|P]]'''. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization.

The difference between '''FP''' and '''P''' is that problems in '''P''' have one-bit, yes/no answers, while problems in '''FP''' can have any output that can be computed in polynomial time. For example, adding two numbers is an '''FP''' problem, while determining if their sum is odd is in '''P'''.<ref>{{cite book | last=Bürgisser | first=Peter | title=Completeness and reduction in algebraic complexity theory | zbl=0948.68082 | series=Algorithms and Computation in Mathematics | volume=7 | location=Berlin | publisher=[[Springer-Verlag]] | year=2000 | isbn=3-540-66752-0 | page=66 }}</ref>

Polynomial-time function problems are fundamental in defining [[polynomial-time reduction]]s, which are used in turn to define the class of [[NP-complete]] problems.<ref>{{cite book | first=Elaine | last=Rich |author-link=Elaine Rich| title=Automata, computability and complexity: theory and applications | publisher=Prentice Hall | year=2008 | isbn=978-0-13-228806-4 | chapter=28.10 "The problem classes FP and FNP" | pages=689–694 | url=http://www.theoryandapplications.org/ }}</ref>