<p>If $\text{#PE}$ is closed under decrement then $\text P=\text{NP}$: consider $\text{#SAT}+1$. Conversely if $\text P=\text{NP}$ then $\text{#PE}=\text{#P}$ is closed under decrement because we can always find an accepting path if one exists then ignore it.</p>

<p>I don't know whether $f\in\text{#PE}$ always implies $f_{-1}\in\text{#P}$. Your $M$ might not provide an accepting path for us to ignore.</p>

CC BY-SA 3.0
2017-06-13T14:51:09.583Z
I do not understand your proof that #PE is closed under decrement implies P=NP. What do you mean by consider #SAT + 1?
Turbo
CC BY-SA 3.0
2017-06-23T13:01:47.697Z
@Turbo: I mean a language like SAT but with one extra accepting path. For example the witnesses could be $(t,y_1,...,y_n)$ where either: ($t=0=y_1=\dots=y_n=0$) or ($t=1$ and $(y_1,...y_n)$ is a witness for the input SAT formula).
Colin McQuillan
CC BY-SA 3.0
2017-06-24T04:24:02.357Z
@ColnMcQuillan Ok I see it. Since $\#SAT_{new}=\#SAT_{given} + 1$ is in $\#PE$ ($SAT_{new}$ is new $SAT$ instance by adding an accepting path to $SAT_{given}$ and this always puts $SAT_{new}$ in $YES$ instance and so decision is in $P$) then if $\#PE$ is closed we have $\#SAT_{given}=\#SAT_{new}-1$ in $\#PE$ which implies $SAT_{given}$ is in $P$ and since $SAT_{given}$ is arbitrary so $P=NP$. is this what you intend? That is a neat non-constructive existence proof.
Turbo
CC BY-SA 3.0
2013-01-02T16:13:52.500Z
2013-01-02T16:13:52.500Z
Colin McQuillan
<p>Given a function $f : \Sigma^* \to \mathbb{N}$, define function $f_{-1}$ as: $f_{-1}(x) = f(x) - 1$ if $f(x) &gt; 0$, and $f_{-1}(x) = 0$ otherwise. Moreover, say that a class ${\cal C}$ of functions is closed under decrement if for every $f \in {\cal C}$, it holds that $f_{-1} \in {\cal C}$. </p>

<p>Define $\#\text{PE}$ [2,3] as the class of functions in $\#\text{P}$ with easy decision versions, that is, the class of functions $f \in \#\text{P}$ for which there exists a polynomial-time deterministic TM $M$ such that $L(M) = \{ x \in \Sigma^* \mid f(x) &gt; 0 \}$. It was shown in [1] that if $\#\text{P}$ is closed under decrement, then $\text{NP} \subseteq \text{SPP}$. But the ideas in the proof of this result cannot be used to provide evidence that  $\#\text{PE}$ is not closed under decrement. So I was wondering what is known about this problem. Is $\#\text{PE}$ closed under decrement? Can at least one prove that if $f \in \#\text{PE}$, then $f_{-1} \in \#\text{P}$? Any help with this would be greatly appreciate it. </p>

<p>[1] Mitsunori Ogiwara, Lane A. Hemachandra: A Complexity Theory for Feasible Closure Properties. J. Comput. Syst. Sci. 46(3): 295-325 (1993)</p>

<p>[2] Aris Pagourtzis. On the complexity of Hard Counting Problems with Easy Decision Version. In Proceedings of the 3rd Panhellenic Logic Symposium,  2001.</p>

<p>[3] Aris Pagourtzis, Stathis Zachos: The Complexity of Counting Functions with Easy Decision Version. MFCS 2006: 741-752</p>

<counting-complexity>
Is #PE (#P Easy) closed under decrement?
Marcelo
# Is #PE (#P Easy) closed under decrement?

(Asked by: username_0 on 2013-01-02)

Given a function $f : \Sigma^\* \to \mathbb{N}$, define function $f\_{-1}$ as: $f\_{-1}(x) = f(x) - 1$ if $f(x) > 0$, and $f\_{-1}(x) = 0$ otherwise. Moreover, say that a class ${\cal C}$ of functions is closed under decrement if for every $f \in {\cal C}$, it holds that $f\_{-1} \in {\cal C}$.

Define $\#\text{PE}$ [2,3] as the class of functions in $\#\text{P}$ with easy decision versions, that is, the class of functions $f \in \#\text{P}$ for which there exists a polynomial-time deterministic TM $M$ such that $L(M) = \{ x \in \Sigma^\* \mid f(x) > 0 \}$. It was shown in [1] that if $\#\text{P}$ is closed under decrement, then $\text{NP} \subseteq \text{SPP}$. But the ideas in the proof of this result cannot be used to provide evidence that $\#\text{PE}$ is not closed under decrement. So I was wondering what is known about this problem. Is $\#\text{PE}$ closed under decrement? Can at least one prove that if $f \in \#\text{PE}$, then $f\_{-1} \in \#\text{P}$? Any help with this would be greatly appreciate it.

[1] Mitsunori Ogiwara, Lane A. Hemachandra: A Complexity Theory for Feasible Closure Properties. J. Comput. Syst. Sci. 46(3): 295-325 (1993)

[2] Aris Pagourtzis. On the complexity of Hard Counting Problems with Easy Decision Version. In Proceedings of the 3rd Panhellenic Logic Symposium, 2001.

[3] Aris Pagourtzis, Stathis Zachos: The Complexity of Counting Functions with Easy Decision Version. MFCS 2006: 741-752

**Tags:** counting-complexity

---

## 1 answers

### Answer by username_1 on 2013-01-02. Score: 6

If $\text{#PE}$ is closed under decrement then $\text P=\text{NP}$: consider $\text{#SAT}+1$. Conversely if $\text P=\text{NP}$ then $\text{#PE}=\text{#P}$ is closed under decrement because we can always find an accepting path if one exists then ignore it.

I don't know whether $f\in\text{#PE}$ always implies $f\_{-1}\in\text{#P}$. Your $M$ might not provide an accepting path for us to ignore.

> **Comments:**
> **username_2**: I do not understand your proof that #PE is closed under decrement implies P=NP. What do you mean by consider #SAT + 1?  
> **username_1**: @Turbo: I mean a language like SAT but with one extra accepting path. For example the witnesses could be $(t,y_1,...,y_n)$ where either: ($t=0=y_1=\dots=y_n=0$) or ($t=1$ and $(y_1,...y_n)$ is a witness for the input SAT formula).  
> **username_2**: @ColnMcQuillan Ok I see it. Since $\#SAT_{new}=\#SAT_{given} + 1$ is in $\#PE$ ($SAT_{new}$ is new $SAT$ instance by adding an accepting path to $SAT_{given}$ and this always puts $SAT_{new}$ in $YES$ instance and so decision is in $P$) then if $\#PE$ is closed we have $\#SAT_{given}=\#SAT_{new}-1$ in $\#PE$ which implies $SAT_{given}$ is in $P$ and since $SAT_{given}$ is arbitrary so $P=NP$. is this what you intend? That is a neat non-constructive existence proof.  

---

