# Tag Info

Accepted

### What's the complexity of counting odd nodes in graph?

Well, at least $\#\mathsf{P}$-hard. Given a SAT formula, construct a graph with two vertices, $v_x$ and $v_x'$, for every possible assignment of variables $\vec{x}$. If $x$ is a satisfying assignment ...
• 7,140
Accepted

Your problem is equivalent to End-of-Metered-Line. This can be shown by reducing your problem to End-of-Potential-Line (see https://arxiv.org/abs/1702.06017). This is a version of End-of-the-Line ...

### Proof refutation: Amateur reviews of ambitious CoRR papers

If you make an arXiv trackback you will not be ignored, in the sense that future readers of the ambitious arXiv paper may check the trackbacks. You even get a mild form of peer review for your posts, ...
• 4,435
Accepted

### Does PPAD really capture the notion of finding another unbalanced vertex?

The problems have been proved to be equivalent (and thus PPAD-complete), see Section 8 in The Hairy Ball Problem is PPAD-Complete by Paul W. Goldberg and Alexandros Hollender.
• 13.8k

### Does PPAD really capture the notion of finding another unbalanced vertex?

This is an interesting question, and I can only give a partial answer. It is easy to see that the construction on p. 505 of Papadimitriou’s paper shows the equivalence of AUV with its special case ...
• 15.3k
Accepted

### What does $\#P\subseteq FP^{PPAD}$ imply?

First, $\mathrm{PPAD\subseteq FP^{NP}}$, hence $\mathrm{\#P^{PPAD}\subseteq\#P^{NP}\subseteq FP^{\#P}}$. Moreover, $\mathrm{PPAD}$ is closed under Turing reductions, i.e., \$\mathrm{FP^{PPAD}\subseteq ...
• 15.3k