Hot answers tagged

10 votes
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
7 votes
Accepted

Is End-of-Monotone-Line PPAD-complete?

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 ...
6 votes

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 votes
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
4 votes

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 ...
3 votes
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 ...
2 votes

Proof refutation: Amateur reviews of ambitious CoRR papers

The ScienceOpen website has a page for most arXiv articles (e.g., here), and it has an option where you can post your own review of any preprint. I do not know if they are recommendable or not (but ...
  • 7,942
2 votes

Are there PPAD-complete puzzles?

In the most authoritative reference on PPAD-complete problems, there is no PPAD-complete puzzle mentioned.
  • 161

Only top scored, non community-wiki answers of a minimum length are eligible