Let FP be the class of functions $f : \{0,1\}^* \to \mathbb{N}$ that can be computed in polynomial time. Moreover, given two functions $f : \{0,1\}^* \to \mathbb{N}$ and $g : \{0,1\}^* \to \mathbb{N}$, we say that there exists a logspace parsimonious reduction from $f$ to $g$ if there exists a function $h : \{0,1\}^* \to \{0,1\}^*$ such that $h$ can be computed in logspace and $f(x) = g(h(x))$ for every $x \in \{0,1\}^*$.

I would appreciate it if someone could give me some references for problems that are complete for FP under logspace parsimonious reductions (or logspace Turing reductions).

  • $\begingroup$ I should have added that FP-completeness should be under logspace parsimonious or Turing reductions. $\endgroup$ – Alejandro Sep 5 '19 at 18:38
  • 1
    $\begingroup$ What does "parsimonious" mean in this context? In the context of NP, it means preserving number of witnesses. But in the context of FP, I suppose it could mean a variety of different things... $\endgroup$ – Joshua Grochow Sep 5 '19 at 18:52
  • 3
    $\begingroup$ For a start, the following is FP-complete: given a constant Boolean circuit with multiple output nodes, compute its output. You may further restrict it to monotone circuits. More generally, if $L$ is any P-complete language (under logspace many-one reductions), then the following problem is FP-complete (under logspace parsimonious reductions): given a sequence of inputs, compute the sequence of bits indicating which of the inputs are in $L$. $\endgroup$ – Emil Jeřábek Sep 5 '19 at 21:10
  • 1
    $\begingroup$ @EmilJeřábek: I think that's an answer (but I think the question may be borderline for cs.SE). $\endgroup$ – Joshua Grochow Sep 5 '19 at 22:57
  • 1
    $\begingroup$ @JoshuaGrochow Well, the OP asked for references, of which I have offered none. $\endgroup$ – Emil Jeřábek Sep 6 '19 at 6:55

Your Answer

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

Browse other questions tagged or ask your own question.