2
$\begingroup$

Given $f: \omega ‎\rightarrow‎ \omega$ , what is the relationship between the following two notions:

(i) the computational complexity of f (in the standard sense, say with naturals represented in binary)

(ii) the computational complexity of the decision problem of the graph $G(f) = \{(x, f(x)) : x \in w \}$ (also with naturals represented in binary).

It is clear that (ii) can be bounded if I know (i) but it is not clear at all how it could work the other way around.

Improve this question
$\endgroup$
5
  • $\begingroup$ Hi, this is not a research level question and thus it is better suited to math.stackexchange.com. Ask it again there and pay attention to the posting guidelines, I am quite sure that it has been answered before. $\endgroup$
    – Dino Rossegger
    Apr 5, 2018 at 9:01
  • 1
    $\begingroup$ @Dino Rossegger: I disagree. Subrecursive degree theory is build precisely on the fact that (ii) is easier than (i). See e.g. the work of Kristiansen: folk.uio.no/larsk/publik.html $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Apr 5, 2018 at 14:57
  • $\begingroup$ @Jan-ChristophSchlage-Puchta, So you mean that the complexity class of (i) is upper than the one which (ii) belongs it?! $\endgroup$
    – Yuval
    Apr 5, 2018 at 23:10
  • $\begingroup$ If you can compute $f(x)$ with effort (e.g. time, memory, size of a finite automaton, ... ) bounded by some function $g(x)$, then you can decide whether a pair $(x, y)$ satisfies $f(x)=y$ with effort bounded by the same function $g$ applied to some (reasonable) coding of $(x,y)$. If $f$ is growing quickly, the coding will be larger than $x$, thus checking is in a smaller class. For example, $n\mapsto 2^{2^n}$ needs at least exponential time, but checking whether $2^{2^n}=m$ requires time polynomial in $m$. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Apr 6, 2018 at 9:27
  • $\begingroup$ @Jan-ChristophSchlage-Puchta Thanks alot. $\endgroup$
    – Yuval
    Apr 8, 2018 at 1:09

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.