The complexity of checking whether two DAG have the same number of topological sorts

This problem is highly related to the CNF one.

Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No".

Intuitively, the complexity of this problem is $C_=P$-complete, just as the CNF one. It is easy to see it is in $C_=P$, but is it $C_=P$-hard?

• @Mike Chen Could you, please, explain what is $C_=P$? And what do you mean by the "counting of topological sorts"? Nov 17 '10 at 22:34
• @Oleksandr: I added a link to $C_=P$ in the question. "counting of topological sorts" means the number of topological sorts. Nov 17 '10 at 22:44
• Right, the counting version of this problem is $\#P$-complete. But what I really wanna know is if counting of solutions is $\#P$-complete, is the problem of deciding whether two have the same number of solutions $C_=P$-complete? Nov 17 '10 at 22:59
• You probably already know this, but let me write this down for others: this problem is not (apparently) the same as the other question on deciding whether two CNF formulas have the same number of solutions. The reason is that counting the solutions to a given CNF formula is #P-complete under parsimonious reductions whereas counting the topological sorts of a given DAG is not (unless P=NP). Counting the topological sorts is #P-complete only under functional reductions between counting problems (also called weakly parsimonious reductions). Dec 2 '10 at 4:42
• Somewhat related: Deciding whether two unweighted graphs have the same number of perfect matchings is C=P-complete. Like in your problem, the counting problem here is also not #P-complete under parsimonious reductions. arxiv.org/abs/1511.07480 Feb 8 '16 at 23:34