In contrast, deciding the existence of a PC directed path is NP-complete, even
when we assume that the input has no PC circuit, as shown
in [1]}. From this, we deduce that finding
an alternating circuit (i.e. directed cycle) for a (certain notion of)
perfect matching in a directed graph is NP-complete (thm:alt-circuit-np)
(and as a corollary, this is also the case for directed paths). Though our
reduction is pretty straightforward, and the statement itself might seem
unsurprising, we have proved it as a step in a possibly much more significant
result that we obtain in [2]}: the refutation of an old
conjecture in proof theory, namely the equivalence between pomset logic and
system BV, see [3]}Though this
paper [3]} was published in 2007, it has its origins
in a technical report from the late 1990's which already contained this
conjecture. (though at the time of writing, we are not entirely sure that our
refutation is correct). This is why we propose in [2]} an
alternative and more direct NP-hardness proof for alternating circuits by
reduction from CNF-SAT, in order to make the proofreading of this latter paper
more self-contained and avoid relying on [1]}.
