# Is #PE (#P Easy) closed under decrement?

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

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.
• @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). Jun 23, 2017 at 13:01
• @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. Jun 24, 2017 at 4:24