# Complete problems for FP

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).

• I should have added that FP-completeness should be under logspace parsimonious or Turing reductions. – Alejandro Sep 5 at 18:38
• 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... – Joshua Grochow Sep 5 at 18:52
• 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$. – Emil Jeřábek supports Monica Sep 5 at 21:10
• @EmilJeřábek: I think that's an answer (but I think the question may be borderline for cs.SE). – Joshua Grochow Sep 5 at 22:57
• @JoshuaGrochow Well, the OP asked for references, of which I have offered none. – Emil Jeřábek supports Monica Sep 6 at 6:55