<p>There is an article from Alan Selman: <a href="http://dx.doi.org/10.1016/S0022-0000(05)80009-1" rel="nofollow noreferrer">A taxonomy of complexity classes of functions</a></p>

<p>Please note, that i found this reference in an Answer (by <a href="https://cstheory.stackexchange.com/users/129/joshua-grochow">Joshua Grochow</a>) for this Question:</p>

<p><a href="https://cstheory.stackexchange.com/questions/5653/complexity-class-when-reducing-decision-problem-to-function-problem">Complexity class when reducing decision problem to function problem</a></p>

<p>Note also the Comments from <a href="https://cstheory.stackexchange.com/users/186/kaveh">Kaveh</a>:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>if i found more, i will add it here.</p>

CC BY-SA 3.0
2016-08-02T20:02:20.263Z
2016-08-02T20:02:20.263Z
2017-04-13T12:32:28.077Z
Landarzar
<p>There are some cstheory questions that touches function-problems. Like this:
<a href="https://cstheory.stackexchange.com/questions/6055/complexity-class-corresponding-to-sorting/6062#6062">Complexity class corresponding to sorting</a></p>

<p>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.</p>

CC BY-SA 3.0
2016-08-02T09:10:54.873Z
There are particular classes that are pretty well-studied: #P ("sharp-P"), PPAD, ....
usul
CC BY-SA 3.0
2016-08-02T09:47:28.167Z
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.
Kaveh
CC BY-SA 3.0
2016-08-02T09:50:36.183Z
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.
Kaveh
CC BY-SA 3.0
2016-08-05T02:38:33.933Z
@Kaveh: Usually, true, but there are some interesting exceptions: http://cstheory.stackexchange.com/a/5656/129.
Joshua Grochow
<cc.complexity-theory><complexity-classes><function>
Is there any good literature on the computational complexity of function problems?
Landarzar
# Is there any good literature on the computational complexity of function problems?

(Asked by: username_0 on 2016-08-01)

There are some cstheory questions that touches function-problems. Like this:
[Complexity class corresponding to sorting](https://cstheory.stackexchange.com/questions/6055/complexity-class-corresponding-to-sorting/6062#6062)

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.

**Tags:** cc.complexity-theory, complexity-classes, function

> **Comments:**
> **username_1**: There are particular classes that are pretty well-studied: #P ("sharp-P"), PPAD, ....  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_3**: @username_2: Usually, true, but there are some interesting exceptions: http://cstheory.stackexchange.com/a/5656/129.  

---

## 1 answers

### Answer by username_0 on 2016-08-02. Score: 4

There is an article from Alan Selman: [A taxonomy of complexity classes of functions](http://dx.doi.org/10.1016/S0022-0000(05)80009-1)

Please note, that i found this reference in an Answer (by [username_3](https://cstheory.stackexchange.com/users/129/joshua-grochow)) for this Question:

[Complexity class when reducing decision problem to function problem](https://cstheory.stackexchange.com/questions/5653/complexity-class-when-reducing-decision-problem-to-function-problem)

Note also the Comments from [username_2](https://cstheory.stackexchange.com/users/186/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.


---

