Hot answers tagged

11

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 for the formula, draw an edge between $v_x$ and $v_x'$; these are the only edges. It is easy to construct the circuit for this graph from the SAT formula, and ...


10

$\def\ac{\mathrm{AC}^0}$Yes, $\ac\mathrm{PAD}=\mathrm{PPAD}$. (Here and below, I’m assuming $\ac$ is defined as a uniform class. Of course, with nonuniform $\ac$ we’d just get $\mathrm{PPAD/poly}$.) The basic idea is quite simple: $\ac$ can do one step of a Turing machine computation, hence we can simulate one polynomial-time computable edge by a ...


7

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 where the line is equipped with a potential function, and a solution is either the end of a line, or a vertex on the line at which the potential function ...


6

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, since they write: Because of widespread Trackback spam we have a semi-automated editorial process that approves trackbacks for display. As for where to ...


5

The following paper at least formalizes the notion of approximate equilibria being close to exact equilibria, and proves some related structural results. Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, and Santosh Vempala (2010). On Nash equilibria of approximation-stable games. In Proceedings of the Third international conference on ...


4

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.


4

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 MANY ENDS OF THE LINE (MEOL): Given a directed graph $G$ with in-degree and out-degree at most $1$ (represented by circuits as above), and a nonempty set $X$ ...


3

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 PPAD}$. Thus, if we assume $$\mathrm{\#P\subseteq PPAD},$$ then $$\mathrm{\#P^{PPAD}\subseteq PPAD},$$ which by induction implies $$\mathrm{FCH=PPAD}.$$ Passing ...


2

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 it seems that all hosted content is under a CC BY license), and I don't know if anyone would notice if you did it, but it exists.


2

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


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