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?

  • $\begingroup$ @Mike Chen Could you, please, explain what is $C_=P$? And what do you mean by the "counting of topological sorts"? $\endgroup$ Nov 17, 2010 at 22:34
  • 2
    $\begingroup$ 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? $\endgroup$
    – Mike Chen
    Nov 17, 2010 at 22:59
  • 4
    $\begingroup$ 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). $\endgroup$ Dec 2, 2010 at 4:42
  • 2
    $\begingroup$ 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 $\endgroup$ Feb 8, 2016 at 23:34
  • 1
    $\begingroup$ The C=P is now broken and was probably moved to complexityzoo.net/…. $\endgroup$ Mar 26, 2022 at 21:34


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.