3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ There are particular classes that are pretty well-studied: #P ("sharp-P"), PPAD, .... $\endgroup$ – usul Aug 2 '16 at 9:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Aug 2 '16 at 9:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Aug 2 '16 at 9:50
  • $\begingroup$ @Kaveh: Usually, true, but there are some interesting exceptions: cstheory.stackexchange.com/a/5656/129. $\endgroup$ – Joshua Grochow Aug 5 '16 at 2:38
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.