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

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

CC BY-SA 4.0
2019-09-05T18:38:12.237Z
I should have added that FP-completeness should be under logspace parsimonious or Turing reductions.
Alejandro
CC BY-SA 4.0
2019-09-05T18:52:25.197Z
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
CC BY-SA 4.0
2019-09-05T20:06:18.443Z
I changed the text to make it  more clear, and in particular to explain what I mean by logspace parsimonious reductions.
Alejandro
CC BY-SA 4.0
2019-09-05T21:10:46.957Z
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
CC BY-SA 4.0
2019-09-05T22:57:35.363Z
@EmilJeřábek: I think that's an answer (but I think the question may be borderline for cs.SE).
Joshua Grochow
CC BY-SA 4.0
2019-09-06T06:55:18.860Z
@JoshuaGrochow Well, the OP asked for *references*, of which I have offered none.
Emil Jeřábek
CC BY-SA 4.0
2019-09-06T15:49:12.513Z
@Alejandro: Do you actually want *references*, or you just want some FP-complete problems?
Joshua Grochow
CC BY-SA 4.0
2019-09-07T20:03:13.570Z
Thanks for your answers!  Both references and FP-complete problems would be useful.
Alejandro
<counting-complexity>
Complete problems for FP
Alejandro
# Complete problems for FP

(Asked by: username_0 on 2019-09-05)

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

**Tags:** counting-complexity

> **Comments:**
> **username_0**: I should have added that FP-completeness should be under logspace parsimonious or Turing reductions.  
> **username_1**: 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...  
> **username_0**: I changed the text to make it  more clear, and in particular to explain what I mean by logspace parsimonious reductions.  
> **username_2**: 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$.  
> **username_1**: @EmilJeřábek: I think that's an answer (but I think the question may be borderline for cs.SE).  
> **username_2**: @JoshuaGrochow Well, the OP asked for *references*, of which I have offered none.  
> **username_1**: @username_0: Do you actually want *references*, or you just want some FP-complete problems?  
> **username_0**: Thanks for your answers!  Both references and FP-complete problems would be useful.  

---

## 0 answers

