Let $G=(V,E)$ be a graph. Let $\Delta_k$ be the quantity defined in this question. Let $\mathcal{C}$ be the set of vertex covers of $G$. The following holds:
$$ |\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k} $$
Let us focus on $\Delta_{|V|}$.
Question
How hard is to compute $\Delta_{|V|}$?
Motivation
The quantity $$\Delta_{|V|}\ \ mod\ \ 2$$ is the parity of the number of vertex covers of $G$. If such quantity is $0$ then $|\mathcal{C}|$ is even, otherwise $|\mathcal{C}|$ is odd.
Therefore (forgive me if I'm wrong):
- Being able to compute $\Delta_{|V|}$ in polynomial time implies $\mathbin{\oplus}$P = P.
- $\Delta_{|V|}$ being $\#$P-hard to compute implies $\mathbin{\oplus}$P = PP.
It seems that in both cases we would get an important result. Clearly there is a third option: computing $\Delta_{|V|}$ may be of intermediate counting complexity, strictly harder than FP but strictly easier than $\#$P-hard.
Update 08/01/2013 21:50
After reading again and more carefully T. Williams' answer to this question, my understanding is that such answer precisely proves that computing $\Delta_{|V|}$ is $\#$P-hard (because the constraint $[0,1,1,1]$ forces every node of $G$ to be present).
However, my second conclusion above does not hold: to conclude $\mathbin{\oplus}$P = PP, computing $\Delta_{|V|}\ \ mod\ \ 2$ should be $\#$P-hard. But the $\#$P-hardness of computing $\Delta_{|V|}$ is not known to imply that computing $\Delta_{|V|}\ \ mod\ \ 2$ is $\#$P-hard as well.
Only a more vague and harmless conclusion can be drawn, more or less along these lines: something which appear to be false from a practical point of view (i.e. Graph Isomorphism $\not\in$ P) would imply something already formally known to be true (i.e. computing $\Delta_{|V|}$ is $\#$P-hard).
