Editing Complexity class (section)

====Important complexity classes====
An important function complexity class is '''[[FP (complexity)|FP]]''', the class of efficiently solvable functions.{{sfn|Arora|Barak|2009|p=344}} More specifically, '''FP''' is the set of function problems that can be solved by a [[deterministic Turing machine]] in [[polynomial time]].{{sfn|Arora|Barak|2009|p=344}} '''FP''' can be thought of as the function problem equivalent of '''[[P (complexity)|P]]'''. Importantly, '''FP''' provides some insight into both counting problems and [[P versus NP|'''P''' versus '''NP''']]. If '''#P'''='''FP''', then the functions that determine the number of certificates for problems in '''NP''' are efficiently solvable. And since computing the number of certificates is at least as hard as determining whether a certificate exists, it must follow that if '''#P'''='''FP''' then '''P'''='''NP''' (it is not known whether this holds in the reverse, i.e. whether '''P'''='''NP''' implies '''#P'''='''FP''').{{sfn|Arora|Barak|2009|p=344}}  

Just as '''FP''' is the function problem equivalent of '''P''', '''[[FNP (complexity)|FNP]]''' is the function problem equivalent of '''[[NP (complexity)|NP]]'''. Importantly, '''FP'''='''FNP''' if and only if '''P'''='''NP'''.{{sfn|Rich|2008|p=689 (510 in provided PDF)}}