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,595
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 ...
- 86
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,475
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.9k
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
...
- 16.9k
4
votes
Accepted
END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node
This class was defined in Papadimitriou's original 1994 paper, that also introduced the class PPAD, and it is known as PPADS. There is an oracle separation between the two classes. For a recent paper ...
- 13.9k
3
votes
How hard is Hex from a symmetric position?
Finding a winning move in symmetric positions in Hex is PSPACE-complete
First, let's define our problem, and call it SYMHEXMOVE:
Take as an input: a symmetric Hex position
Output: any move which is ...
- 156
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 ...
- 16.9k
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 ...
- 8,896
Only top scored, non community-wiki answers of a minimum length are eligible