# Is there any good literature on the computational complexity of function problems?

There are some cstheory questions that touches function-problems. Like this: Complexity class corresponding to sorting

So here is the question: Is there good literature about the computational complexity of functions problems? Especially, but not limited to that, about functions-problems with polynomial space bound.

• There are particular classes that are pretty well-studied: #P ("sharp-P"), PPAD, ....
– usul
Commented Aug 2, 2016 at 9:10
• Function problems very often reduce to a decision problem of similar complexity. That is why they are not studied independently unless there is no good corresponding decision problem. Commented Aug 2, 2016 at 9:47
• If you have a function you can look at the bit graph of the function which is a decision problem. If you can compute the function you can compute the bit graph easily from it. If you can compute the bit graph you can compute the function by simple computing the bits of the output one by one. Commented Aug 2, 2016 at 9:50
• @Kaveh: Usually, true, but there are some interesting exceptions: cstheory.stackexchange.com/a/5656/129. Commented Aug 5, 2016 at 2:38

## 1 Answer

There is an article from Alan Selman: A taxonomy of complexity classes of functions

Please note, that i found this reference in an Answer (by Joshua Grochow) for this Question:

Complexity class when reducing decision problem to function problem

Note also the Comments from Kaveh:

If you have a function you can look at the bit graph of the function which is a decision problem. If you can compute the function you can compute the bit graph easily from it. If you can compute the bit graph you can compute the function by simple computing the bits of the output one by one.

if i found more, i will add it here.